[Python-de] Denksportaufgabe: Beschraenktes Sortieren

Dinu Gherman gherman at darwin.in-berlin.de
Fri May 9 11:47:37 EDT 2003


Dinu Gherman:

> Geht, aber dann muss man zwei sort-Funktionen haben oder eine mit
> Fallabfrage, isinstance(), oder so. Schoener finde ich, das der
> Struct-Klasse zu ueberlassen, und __getitem__ auf __getattr__ um-
> zubiegen! ;-)

Folgendes habe ich gemeint. Fuer mich sieht das nach einer sauberen
OO-Loesung aus, denn die sort-Funktion muss nicht angepasst werden:

# -----------------------------------------------------
class Struct:
     """A struct class mapping element indexing to attribute access.

     s = Struct(foo="bar")
     s["foo"] == "bar" -> 1
     """

     # could also implement setattr, delattr, setitem, delitem

     def __init__(self, **kwDict):
         "Init with provided key/value pairs, if any."
         self._keys = []
         for k, v in kwDict.items():
             setattr(self, k, v)
             self._keys.append(k)

     def __getitem__(self, name):
         "Redirect element indexing to attribute access."
         return getattr(self, name)

     # needed only for testing
     def __eq__(self, other):
         "Compare two struct instances based on the wrapped keys."
          # unique() defined elsewhere...
         keys = unique(self._keys + other._keys)
         return reduce(lambda x,y:x or y, [self[k]==other[k] for k in 
keys])
# -----------------------------------------------------

> Ich halte meine Loesung noch eine Weile zurueck, falls sich noch
> andere daran versuchen wollen.

Hier also meine Version der sort-Funktion (koennte man auch mit vier
Zeilen im Korpus schreiben, oder mit lambdas statt list comprehen-
sions):

# -----------------------------------------------------
def sort(seq, indices=[]):
     id = range(len(seq))
     decorated = [([seq[j][i] for i in indices], j) for j in id]
     decorated.sort()
     perm = [k for (criteria, k) in decorated]
     sorted = [seq[perm[j]] for j in id]
     return sorted
# -----------------------------------------------------

Der Knackpunkt ist, dass man in 'decorated' nur die zu sortierenden
Felder uebernimmt und rechts davon nur noch eine "Identitaetspermu-
tation" 'id' anfuegt. Diese wird mitsortiert und kann auf die Aus-
gangssequenz angewendet werden. Eine weiterfuehrende Uebung: wieso
klappt das auch mit Strings?

Die einfachere Variante, bei der nach allen Feldern sortiert wird,
kommt auch in "Python Nutshell" (O'Reilly) vor (S. 401), mit einem
vagen Hinweis auf die obige Fassung, wie ich gestern festgestellt
habe (danke, Giorgio!).

Letztlich machen wir damit so eine Art SQL-Abfrage folgender Art:
"SELECT * FROM seq ORDER BY indices" - mal abgesehen davon, dass
die Zeilen einer SQL-Tabelle per se keine direkte Ordnung haben.

Wer weiterknobeln will: finde eine Funktion group(seq, indices=[])
mit aehnlichen Nebeneigenschaften wie bisher, die folgende SQL-
Abfrage implementiert: "SELECT * FROM seq GROUP BY indices". Bei-
spiel (jedenfalls erwarte ich, dass das in SQL so etwas macht ;-):

# -----------------------------------------------------
class TestGroup(unittest.TestCase):
     "Test group() function."

     def testGroup(self):
         "Test group()."

         input = [[1, 1, 1, 2],
                  [2, 0, 2, 3],
                  [0, 1, 3, 0],
                  [2, 0, 0, 1]]
         exp = [[[1, 1, 1, 2]],
                [[2, 0, 2, 3],
                 [2, 0, 0, 1]],
                [[0, 1, 3, 0]]]
         result = group(input, [1, 0])
         self.assert_(result == exp)
# -----------------------------------------------------

Ich habe da eine Version, aber die sieht noch sehr gespenstisch aus!

Viel Vergnuegen,

Dinu

--
Dinu C. Gherman
......................................................................
"Les gens se divisent en deux catégories : les uns cherchent et
ne trouvent pas, les autres trouvent et ne sont pas contents."
(Mihail Eminescu)





More information about the Python-de mailing list