Seite 1 von 1
datenstruktur für Start und Endposition
Verfasst: Montag 10. Mai 2010, 11:39
von mit
Hallo,
ich habe folgende Datei:
Jeder Zeile beinhaltet eine String welcher als Rückgabewert dient, Start und Endposition.
Der Benutzer gibt z. B. als Startwert 7 und als Endwert 9 und dann sollte er s2 als Antwort erhalten. Lieder weiss ich nicht wie man am besten den Inhalt dieser Datei in eine Datenstruktur packen könnte.
Viele Grüße
Re: datenstruktur für Start und Endposition
Verfasst: Montag 10. Mai 2010, 11:41
von ms4py
`dict` mit tuple der Werte als key und string als Wert.
Code: Alles auswählen
>>> example = { (4, 7) : 's1',
... (3, 8) : 's2' }
>>> example[(3,8)]
's2'
Re: datenstruktur für Start und Endposition
Verfasst: Montag 10. Mai 2010, 12:04
von .robert
Hi,
in welchen Größenordnungen bewegst du dich denn? Und was soll passieren, wenn Start- und Endwert in verschiedenen Bereichen liegen?
Vielleicht ist für dich eine einfache Liste das beste:
Code: Alles auswählen
mapping = ['s1','s1','s1','s1','s1','s2','s2','s2','s2','s2','s3','s3','s3','s3','s3']
def get_area(startpos, endpos):
a = mapping[startpos]
b = mapping[endpos]
if a == b:
return a
else:
## hier behandlung für verschiedene areas
so in etwa...
Re: datenstruktur für Start und Endposition
Verfasst: Montag 10. Mai 2010, 12:10
von jbs
Code: Alles auswählen
example = {'s1': (1,5), 's2': (6,10), 's3':(11,15)}
user_input = 7,9
def get_fitting(user_input):
for k, v in example.iteritems():
if v[0] <= user_input[0] and v[1] >= user_input[1]:
yield k
print list(get_fitting(user_input))
Re: datenstruktur für Start und Endposition
Verfasst: Montag 10. Mai 2010, 12:22
von HerrHagen
Re: datenstruktur für Start und Endposition
Verfasst: Montag 10. Mai 2010, 13:27
von mit
Danke `dict` mit tuple scheint zu funktionieren, aber wie bekomme ich Daten in diese Struktur eingefügt? Und warum funktioniert yield und nicht return?
Code: Alles auswählen
example = {'s1': (1,5), 's2': (6,10), 's3':(11,15)}
user_input = 7,9
inputFile = """
s1 1 5
s2 6 10
s3 11 15
"""
def get_fitting(user_input):
for k, v in example.iteritems():
print k
if v[0] <= user_input[0] and v[1] >= user_input[1]:
yield k
for line in inputFile.rstrip().split('\t'):
print line
print list(get_fitting(user_input))
Leider verstehe ich nicht bisect.
Re: datenstruktur für Start und Endposition
Verfasst: Montag 10. Mai 2010, 13:59
von BlackJack
@mit: Wie man die Daten in das Dictionary bekommt ist echt trivial. Das sind absolute Grundlagen, die solltest Du Dir schon erarbeiten. IMHO.
Re: datenstruktur für Start und Endposition
Verfasst: Montag 10. Mai 2010, 14:04
von ms4py
Mal als Anregung
Code: Alles auswählen
>>> inputFile = """
... s1 1 5
... s2 6 10
... s3 11 15
... """
>>> for line in inputFile.splitlines():
... line.split()
...
[]
['s1', '1', '5']
['s2', '6', '10']
['s3', '11', '15']
P.S. Normalerweise sollte die Variable "input_file" benannt werden. Schau dir mal PEP8 an.
Re: datenstruktur für Start und Endposition
Verfasst: Montag 10. Mai 2010, 14:46
von /me
Re: datenstruktur für Start und Endposition
Verfasst: Montag 10. Mai 2010, 15:28
von Nagila Hawa
Deiner Problembeschreibung fehlen ein paar Informationen. Vor Allem, wurde schon einmal gefragt, was denn passieren soll, wenn der Nutzer beispielsweise 1 und 11 eingibt. Dann liegt das in mehreren Bereichen. Von dem, was ich sehen kann, könnte dir aber Folgendes helfen:
"f(x) = (x - 1) div 5" gibt dir den Bereich an, mit Startwert 0. Du kannst das noch einmal inkrementieren, wenn dir der Startwert 1 wichtig ist.
Re: datenstruktur für Start und Endposition
Verfasst: Dienstag 11. Mai 2010, 10:56
von mit
@Nagila Hawa: Du hast Recht meine Problembeschreibung war nicht gut.
* Wenn user_input1 = 7,9 ist dann sollte das Ergebnis "s2, 2, 4" sein, d.h. 7 ist die zweite Position in s2 und 9 ist die 4 Position s2
* Wenn user_input2 = 7,12 ist dann sollte das Ergebnis "s2, 2, 5" und "s3, 1, 2" sein, d.h. 7 ist die zweite Position, aber 12 ist nicht in s2 deshalb wird die Endposition auf 5 gesetzt und als nächstes wird s3 betrachtet. Von s3 nehmen wir 1 da es die erste position ist 12 (user input) bekommt eine 2.
Ich habe es versucht mit dict und Tuples, aber leider ist dict nicht sortiert und deshalb bin auf List umgestiegen, aber trotzdem bekomme ich nicht die gewünschte ausgabe:
Code: Alles auswählen
def get_fitting(user_input, input_List):
results_List = []
for s in input_List:
if s[1] <= user_input[0] and s[2] >= user_input[1]:
print("HIT")
s_Length = s[2] - s[1] + 1
start_Pos = abs(s_Length - user_input[0])
end_Pos = abs(s_Length - user_input[1])
results_List.append([s[0], start_Pos, end_Pos])
break
elif s[1] <= user_input[0] and s[2] <= user_input[1]:
s_Length = s[2] - s[1] + 1
start_Pos = abs(s_Length - user_input[0])
end_Pos = s[2]
results_List.append([s[0], start_Pos, end_Pos])
print results_List
if __name__ == '__main__':
inputFile = """s1 1 5
s2 6 10
s3 11 15"""
print inputFile
input_List = []
for line in inputFile.splitlines():
line = line.split('\t')
input_List.append([line[0], int(line[1]), int(line[2])])
print "user input 1"
user_input1 = 7,9
get_fitting(user_input1, input_List)
print "user input 2"
user_input2 = 7,12
get_fitting(user_input2, input_List)
Momentan sieht die Ausgabe wie folgt aus:
Code: Alles auswählen
$ python gff.py
s1 1 5
s2 6 10
s3 11 15
user input 1
HIT
[['s1', 2, 5], ['s2', 2, 4]]
user input 2
[['s1', 2, 5], ['s2', 2, 10]]
Wo könnte der Fehler liegen?
Re: datenstruktur für Start und Endposition
Verfasst: Mittwoch 12. Mai 2010, 00:28
von Nagila Hawa
Ich meinte dabei auch zum Beispiel Einschränkungen wie die Bereiche aussehen. Bei deinem Beispiel sind alle Bereiche zusammenhängend und jeweils 5 Elemente groß. Wenn alle Anwendungsfälle derartige Eigenschaften besitzen, kann man die Aufgabe ganz ohne komplexe Datenstrukturen und zum Beispiel mit "div" und "mod" lösen. Ich habe es mal ausprobiert und die Ergebnisse sehen soweit wie gewünscht aus:
Code: Alles auswählen
./bereich.fs 7 52
s2 : 2 .. 5
s3 : 1 .. 5
s4 : 1 .. 5
s5 : 1 .. 5
s6 : 1 .. 5
s7 : 1 .. 5
s8 : 1 .. 5
s9 : 1 .. 5
s10 : 1 .. 5
s11 : 1 .. 2
./bereich 13 21
s3: 3..5
s4: 1..5
s5: 1..1
Diverse Werte sind hier Parametrisierbar: Der allgemeine Startwert, die Anzahl der Elemente pro Bereich, der Index der ersten Position und der Index des ersten Bereichs. Eventuell langt das ja für deinen Einsatz. Effizienter und einfacher als mit Datenstrukturen ist es auf jeden Fall.
Den Code könnte ich auch posten, wenn du willst. Es ist beides kein Python, da ich da schon länger aus der Übung bin.
Das sind jedoch jeweils mit Eingabe nur 25 bzw 45 Zeilen Code und es werden nur einfachste Mittel verwendet.
Re: datenstruktur für Start und Endposition
Verfasst: Mittwoch 12. Mai 2010, 09:07
von mit
Die Bereiche können unterschiedlich groß sein z. B. 100-14000. Der Abstand zwischen zwei Bereichen (z.B. s1 und s2) kann 50 - 200 sein. Beispiel für Eingabedatei:
@Nagila Hawa: Könntest du bitte auch nicht den Python Code posten?
Re: datenstruktur für Start und Endposition
Verfasst: Mittwoch 12. Mai 2010, 15:35
von Nagila Hawa
Das spielt ohnehin keine Rolle, da du ja diese Einschränkungen für die Daten nicht hast. Wie gesagt, sind meine Python-Kenntnisse sehr angestaubt und bewegten sich sowieso nur im einfachen Skriptbereich, daher wäre meine Herangehensweise wohl eher unpythonisch und low-level: Bereich und Position für ersten und zweiten Eingabewert durch Iteration bestimmen und ausgeben, wenn beide in einem Bereich sind, ansonsten die Mittelbereiche unverändert zusätzlich ausgeben.
Also in Pseudocode:
Code: Alles auswählen
Prozedur Berechne Bereich und Position:
Iteriere über die Zeilen in der Datei
Wenn (X >= Startwert) und (X <= Endwert)
Bereich := Bereich der Zeile
Position := Eingabewert - Startwert + 1
Berechne Bereich und Position für Eingabewert 1
Berechne Bereich und Position für Eingabewert 2
Wenn Bereich 1 = Bereich 2
Gebe aus: Bereich 1, Position 1, Position 2
Sonst
Gebe aus: Bereich 1, Position 1, Endwert Bereich 1
Gebe für alle Bereiche X zwischen Bereich 1 und Bereich 2 aus:
Bereich X, Startwert Bereich X, Endwert Bereich X
Gebe aus: Bereich 2, Startwert Bereich 2, Position 2
Wenn du die Bereiche vorher in den Speicher laden willst, was in der Regel ganz praktisch sein könnte, dann nimmst du dafür eine einfache Liste aus einem Record mit Anfangswert und Endwert des Bereiches.
mit hat geschrieben:@Nagila Hawa: Könntest du bitte auch nicht den Python Code posten?
Ich habe doch den Python-Code nicht geposted.
Falls du meinst, ich soll den nicht-Python Code posten. Auch wenn er dir sicher nicht gefällt:
Code: Alles auswählen
#! /usr/bin/env gforth
1 CONSTANT START_VALUE
5 CONSTANT AREA_VALUES
1 CONSTANT FIRST_AREA
1 CONSTANT FIRST_POSITION
AREA_VALUES FIRST_POSITION + 1 - CONSTANT MAX_POSITION
: get-area START_VALUE - AREA_VALUES / FIRST_AREA + ;
: get-position START_VALUE - AREA_VALUES mod FIRST_POSITION + ;
: pos-area dup get-position swap get-area ;
: calculate pos-area rot pos-area ;
: print-single ." s" swap . ." : " swap . ." .. " drop . ;
: print-first ." s" over . ." : " 2swap dup . ." .. " MAX_POSITION . 2swap ;
: print-middle 2dup 2 - <= if over 1 + over swap do
cr ." s" I . ." : " FIRST_POSITION . ." .. " MAX_POSITION .
loop then ;
: print-last cr ." s" . ." : " FIRST_POSITION . ." .. " 2drop . ;
: print-multi print-first print-middle print-last ;
: output rot 2dup = if print-single else print-multi then ;
: print-help ." Brauche 2 Zahlen" ;
: read-argument next-arg s>number? nip ;
: read-input read-argument read-argument rot and ;
: area read-input if calculate output else drop print-help then ;
area cr bye
Code: Alles auswählen
program Bereich;
uses
SysUtils;
const
Start_Value = 1;
Area_Values = 5;
First_Area = 1;
First_Position = 1;
var
Input_First : Integer;
Input_Last : Integer;
Area_First : Integer;
Area_Last : Integer;
Position_First : Integer;
Position_Last : Integer;
I : Integer;
begin
Input_First := StrToInt(ParamStr(1));
Input_Last := StrToInt(ParamStr(2));
Area_First := First_Area + ((Input_First - Start_Value) div Area_Values);
Area_Last := First_Area + ((Input_Last - Start_Value) div Area_Values);
Position_First := First_Position + ((Input_First - Start_Value) mod Area_Values);
Position_Last := First_Position + ((Input_Last - Start_Value) mod Area_Values);
if Area_First = Area_Last then
begin
WriteLn('s', Area_First, ': ', Position_First, '..', Position_Last)
end
else
begin
WriteLn('s', Area_First, ': ', Position_First, '..', Area_Values + First_Position - 1);
for I := Area_First + 1 to Area_Last - 1 do
begin
WriteLn('s', I, ': ', First_Position, '..', Area_Values + First_Position - 1)
end;
WriteLn('s', Area_Last, ': ', First_Position, '..', Position_Last)
end
end.
Re: datenstruktur für Start und Endposition
Verfasst: Donnerstag 13. Mai 2010, 09:34
von mit
Danke für den Pseudo-Code. Leider war ich nicht im Stande das Problem zu Lösen und habe das Problem wie folgt vereinfacht. Jetzt suche ich nur nach den Bereichen die vom Benutzer begrenzt sind, d.h.
* user input 1: 7,9 dann soll das Ergenis s2 sein
* user input 2: 7,12 dann soll das Ergebnis s2 und s3 sein und
* user input3: 3,12 dann soll das Ergebnis s1, s2 und s3 sein
Leider war ich nicht Erfolgreich das Problem zu lösen denn die Ausgabe für den letzten Test müsste aber [['s1'], ['s2'], ['s3']] sein ist aber [['s1'], ['s3']].
Code: Alles auswählen
def get_fitting(user_input, input_List):
results_List = []
for input_File in input_List:
if input_File[1] <= user_input[0] and input_File[2] >= user_input[1]:
results_List.append([input_File[0]])
elif user_input[0] >= input_File[1] and user_input[0] <= input_File[2]:
results_List.append([input_File[0]])
elif user_input[1] >= input_File[1] and user_input[1] <= input_File[2]:
results_List.append([input_File[0]])
return results_List
if __name__ == '__main__':
inputFile = """s1 1 5
s2 6 10
s3 11 15"""
print inputFile
input_List = []
for line in inputFile.splitlines():
line = line.split('\t')
input_List.append([line[0], int(line[1]), int(line[2])])
print "user input 1"
user_input1 = 7,9
results_List = get_fitting(user_input1, input_List)
print results_List
print "user input 2"
user_input2 = 7,12
results_List = get_fitting(user_input2, input_List)
print results_List
print "user input 3"
user_input3 = 3,12
results_List = get_fitting(user_input3, input_List)
print results_List
Leider ist der letzte Test (user_input 3) falsch:
Code: Alles auswählen
s1 1 5
s2 6 10
s3 11 15
user input 1
[['s2']]
user input 2
[['s2'], ['s3']]
user input 3
[['s1'], ['s3']]
Die Ausgabe für den letzten Test müsste aber [['s1'], ['s2'], ['s3']] sein.
Wo liegt der Fehler?
Re: datenstruktur für Start und Endposition
Verfasst: Donnerstag 13. Mai 2010, 22:42
von Nagila Hawa
Wenn du es so machst, gibt es vier mögliche Situationen, in dem du den Bereich zur Liste hinzufügen musst:
- Vordere Grenze vor Bereich, hintere Grenze hinter Bereich
Vordere Grenze vor Bereich, hintere Grenze im Bereich
Vordere Grenze im Bereich, hintere Grenze hinter Bereich
Beide Grenzen im Bereich
Code: Alles auswählen
#! /usr/bin/python
# -*- coding: utf-8 -*-
def get_fitting(bounds, input_list):
result_list = []
for area in input_list:
# Vordere Grenze vor Bereich, hintere Grenze hinter Bereich
if bounds[0] < area[1] and bounds[1] > area[2]:
result_list.append([area[0], area[1], area[2]])
# Vordere Grenze vor Bereich, hintere Grenze im Bereich
elif bounds[0] < area[1] and bounds[1] <= area[2] and bounds[1] >= area[1]:
result_list.append([area[0], area[1], bounds[1]])
# Vordere Grenze im Bereich, hintere Grenze hinter Bereich
elif bounds[0] >= area[1] and bounds[0] <= area[2] and bounds[1] > area[2]:
result_list.append([area[0], bounds[0], area[2]])
# Beide Grenzen im Bereich
elif bounds[0] >= area[1] and bounds[1] <= area[2]:
result_list.append([area[0], bounds[0], bounds[1]])
return result_list
if __name__ == '__main__':
inputFile = """s1;1;5
s2;6;10
s3;11;15"""
print inputFile
input_List = []
for line in inputFile.splitlines():
line = line.split(';')
input_List.append([line[0], int(line[1]), int(line[2])])
print "user input 1"
user_input1 = 7,9
results_List = get_fitting(user_input1, input_List)
print results_List
print "user input 2"
user_input2 = 7,12
results_List = get_fitting(user_input2, input_List)
print results_List
print "user input 3"
user_input3 = 3,12
results_List = get_fitting(user_input3, input_List)
print results_List
Und danke für das Pascal-Highlighting.
Re: datenstruktur für Start und Endposition
Verfasst: Freitag 14. Mai 2010, 09:32
von mit
Vielen dank Nagila Hawa. Es funktioniert.