datenstruktur für Start und Endposition

[mit]

Hallo,
ich habe folgende Datei:

Code: Alles auswählen

s1	1	5
s2	6	10
s3	11	15
.....

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

[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'

[.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...

[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))

[HerrHagen]

Wie wärs damit:
http://docs.python.org/library/bisect.html

[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.

[BlackJack]

@mit: Wie man die Daten in das Dictionary bekommt ist echt trivial. Das sind absolute Grundlagen, die solltest Du Dir schon erarbeiten. IMHO.

[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.

[/me]

Wie wärs damit:
http://docs.python.org/library/bisect.html

bisect ist Klasse.

[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.

[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?

[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.

[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:

Code: Alles auswählen

s1	1	13678
s2	13778	14000
s3	14100	15999

@Nagila Hawa: Könntest du bitte auch nicht den Python Code posten?

[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.

@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.

[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?

[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.

[mit]

Vielen dank Nagila Hawa. Es funktioniert.