Seite 1 von 1
Überschneidungen finden und entfernen
Verfasst: Donnerstag 1. Juli 2010, 17:22
von Twilo
Hallo,
ich habe mehrere PLZ-Bereiche und möchte Überscheidungen finden und beseitigen
aus folgenden Bereichen: 0-10000,14900-15100, 11000-12000,15101, 14000-15000,11500-14500,28001
möchte ich folgendes Ergebnis: 0-10000,11000-15101,28001
Mein Ansatz ist bis jetzt folgender:
Code: Alles auswählen
import re
import string
zipcodeStr = "0-10000,14900-15100, 11000-12000,15101, 14000-15000,11500-14500,28001"
zipcodeStr = zipcodeStr.replace(" ", "")
zipcodeFields = [zipcode for zipcode in zipcodeStr.split(",") if zipcode]
zipcodesList = [0] * 100000
matchStr = re.compile("(\d+)\-(\d+)")
for zipcodeArea in zipcodeFields:
if zipcodeArea.find("-") > 0:
match = matchStr.match(zipcodeArea)
if match:
zipcodeFrom = int(match.group(1))
zipcodeTo = int(match.group(2))
if zipcodeFrom > zipcodeTo:
zipcodeFrom, zipcodeTo = zipcodeTo, zipcodeFrom
for i in range(zipcodeFrom, zipcodeTo + 1):
zipcodesList[i] = 1
else:
print "Wrong Zipcode Area %s" % zipcodeArea
else:
zipcodesList[int(zipcodeArea)] = 1
try:
zipcodesList[int(zipcodeArea)] = 1
except:
print "Wrong Zipcode %s" % zipcodeArea
zipcodeFields = []
zipcodeStart = None
zipcodeEnd = None
for i in range(len(zipcodesList)):
if zipcodesList[i] == 1:
if zipcodeStart is None:
zipcodeStart = i
else:
zipcodeEnd = i
else:
if zipcodeStart is not None:
if zipcodeEnd is not None:
zipcodeFields.append("%d-%d" % (zipcodeStart, zipcodeEnd))
else:
zipcodeFields.append("%d" % (zipcodeStart))
zipcodeStart = None
zipcodeEnd = None
zipcodeStr = string.join(zipcodeFields, ",")
print zipcodeStr
geht das irgendwie eleganter?
Mein Algorithmus ist etwas ineffizient, wenn Bereiche z.B. doppelt angegeben werden oder in ein Bereich zig andere Bereiche fallen. Ich muss auch den höchsten Index kennen, da es sonst zum IndexError kommt.
mfg
Twilo
Re: Überscheidungen finden und entfernen
Verfasst: Donnerstag 1. Juli 2010, 17:43
von EyDu
Da könnte sich noch der ein oder andere kleine Fehler verstecken, ich habe es nicht wirklich getestet.
Code: Alles auswählen
ranges = [(10,15), (12, 20), (18, 30), (18, 20),
(40, 50), (60, 60), (70, 100), (80, 90)]
def merge_ranges(ranges):
tokens = []
for begin, end in ranges:
tokens.append((begin, 1))
tokens.append((end, -1))
tokens.sort()
result = []
stack = 0
for position, value in tokens:
if stack == 0:
begin = position
stack += value
if stack == 0:
result.append((begin, position))
return result
Re: Überscheidungen finden und entfernen
Verfasst: Donnerstag 1. Juli 2010, 18:07
von Defnull
Ungetestet:
Code: Alles auswählen
l = "0-10000,14900-15100, 11000-12000,15101, 14000-15000,11500-14500,28001"
l = [map(int, x.split('-')) if '-' in x else [int(x)]*2 for x in l.split(',')]
def flatten(l):
l = sorted(l)
last = l.pop(0)
for current in l:
if last[0] <= current[0] <= last[1]+1:
last[1] = max(last[1], current[1])
continue
yield last
last = current
yield last
print ', '.join([str(a) if a==b else '%d-%d'%(a, b) for a, b in flatten(l)])
Re: Überscheidungen finden und entfernen
Verfasst: Donnerstag 1. Juli 2010, 18:32
von Barabbas
Ziemlich raffinierte Lösung, finde ich. Aber die LC in Zeile 2 ist tatsächlich mal überflüssig, oder gibt es da eine total abgefahrene Optimierung - kann ja eigentlich nicht, oder? Aber wie gesagt: Nicht schlecht, das muss man sich schon ein paar mal ansehen - ich zumindest
.
Besten Gruß,
bar - "Schleimer" - abbas
Re: Überscheidungen finden und entfernen
Verfasst: Donnerstag 1. Juli 2010, 18:38
von Defnull
Ja, der war komplett überflüssig. Den hab ich wohl beim mehrmaligen Umsortieren des Codes übersehen
Re: Überscheidungen finden und entfernen
Verfasst: Donnerstag 1. Juli 2010, 18:43
von Twilo
Hallo,
Defnull hat geschrieben:Ungetestet:
Code: Alles auswählen
l = "0-10000,14900-15100, 11000-12000,15101, 14000-15000,11500-14500,28001"
l = [map(int, x.split('-')) if '-' in x else [int(x)]*2 for x in l.split(',')]
def flatten(l):
l = sorted(l)
last = l.pop(0)
for current in l:
if last[0] <= current[0] <= last[1]+1:
last[1] = max(last[1], current[1])
continue
yield last
last = current
yield last
print ', '.join([str(a) if a==b else '%d-%d'%(a, b) for a, b in flatten(l)])
ich habs getestet. sieht gut aus
Barabbas hat geschrieben:Ziemlich raffinierte Lösung, finde ich. Aber die LC in Zeile 2 ist tatsächlich mal überflüssig, oder gibt es da eine total abgefahrene Optimierung - kann ja eigentlich nicht, oder?
was meinst Du mit "LC in Zeile 2"?
mfg
Twilo
Re: Überscheidungen finden und entfernen
Verfasst: Donnerstag 1. Juli 2010, 19:18
von Barabbas
Ach, hat sich schon erledigt. Mit "LC" meinte ich "
List Comprehension", falls du das meintest.
Gruß,
brb
Re: Überschneidungen finden und entfernen
Verfasst: Freitag 2. Juli 2010, 00:14
von pillmuncher
Im Wesentlichen dieselbe Logik wie bei Defnull, aber mit
reduce:
Code: Alles auswählen
ds = "0-10000,14900-15100, 11000-12000,15101, 14000-15000,11500-14500,28001"
rs = [map(int, s.split('-')) if '-' in s else [int(s)]*2 for s in ds.split(',')]
def merged(ss):
def merge(ranges, (new_lo, new_hi)): # <-- diese Syntax gibts nicht mehr ab Python 3, AFAIR
old_lo, old_hi = ranges[-1]
if old_hi < new_lo-1:
ranges.append([new_lo, new_hi])
elif old_hi < new_hi:
ranges[-1][1] = new_hi
return ranges
return (lambda head, *tail: reduce(merge, tail, [head]))(*sorted(ss))
print(', '.join([str(a) if a==b else '%d-%d'%(a, b) for a, b in merged(rs)]))
Re: Überschneidungen finden und entfernen
Verfasst: Freitag 2. Juli 2010, 11:22
von Twilo
Hallo,
die Zeile
Code: Alles auswählen
l = [map(int, x.split('-')) if '-' in x else [int(x)]*2 for x in l.split(',')]
funktioniert leider nicht mit python 2.4.
Code: Alles auswählen
Python 2.4.5 (#2, Dec 14 2009, 17:36:33)
[GCC 3.4.6 [FreeBSD] 20060305] on freebsd6
Type "help", "copyright", "credits" or "license" for more information.
>>> l = "0-10000,14900-15100, 11000-12000,15101, 14000-15000,11500-14500,28001"
>>> l = [map(int, x.split('-')) if '-' in x else [int(x)]*2 for x in l.split(',')]
File "<stdin>", line 1
l = [map(int, x.split('-')) if '-' in x else [int(x)]*2 for x in l.split(',')]
^
SyntaxError: invalid syntax
gibt es ein anderen Einzeiler dafür?
Im Moment habe ich den Code wie folgt abgeändert
Code: Alles auswählen
l = []
for x in l.split(','):
if '-' in x:
l.append(map(int, x.split('-')))
else:
l.append([int(x)]*2)
mfg
Twilo
Re: Überschneidungen finden und entfernen
Verfasst: Freitag 2. Juli 2010, 11:50
von Defnull
Twilo hat geschrieben:Code: Alles auswählen
l = [map(int, x.split('-')) if '-' in x else [int(x)]*2 for x in l.split(',')]
funktioniert leider nicht mit python 2.4.
Das sollte auch so gehen:
Code: Alles auswählen
l = ['-' in x and map(int, x.split('-')) or [int(x)]*2 for x in l.split(',')]
Re: Überschneidungen finden und entfernen
Verfasst: Freitag 2. Juli 2010, 14:11
von Twilo
Hallo /dev/null,
ja das funktioniert
Ein Problem habe ich noch, wenn jemand auf die Idee kommt und das Semikolon statt dem Komma zur Trennung verwendet, wird eine Exception geworfen, genauso wenn jemand ausversehen zwei Kommas hinter einander eingibt.
Am Anfang könnte man evtl. folgendes machen
nur wie ersetzte ich mehrere Kommas zu eins? Es ist heute definitiv zu warm
mfg
Twilo
Re: Überschneidungen finden und entfernen
Verfasst: Freitag 2. Juli 2010, 14:16
von Rebecca
Re: Überschneidungen finden und entfernen
Verfasst: Freitag 2. Juli 2010, 15:00
von Twilo
Hallo,
das funktioniert leider nicht, wenn 3 oder mehr Kommata verwendet werden.
Geht das nur mit regulären Ausdrücken?
mfg
Twilo
Re: Überschneidungen finden und entfernen
Verfasst: Freitag 2. Juli 2010, 15:14
von BlackJack
@Twilo: Was ist denn so schlimm daran wenn es bei falschen Eingaben eine Ausnahme gibt? Benutzereingaben still und leise zu korrigieren ist selten eine gute Idee. Wenn der Benutzer etwas falsch eingibt, sollte er darauf hingewiesen werden und die Eingabe sollte zurückgewiesen werden.