Дедупе и сортировка списка в Python 2.2

Question

В Python 2.2 (не спрашивайте), каков самый удобный способ сортировки списка и удаления дубликатов?

Я, очевидно, могу написать функцию, которая будет sort() затем повторяться, но мне интересно, есть ли идиоматическая однострочная.

edit: Список короткий, поэтому эффективность не имеет значения. Также элементы являются неизменяемыми.

Answer 1

Для старых версий Python, и поскольку вы используете строки, я не могу придумать ни одной строки, но шаблон, вероятно, будет таким, используя словари:

def sorted_uniq(your_list):
    table = {}
    for s in your_list:
        table[s] = None
    k = table.keys()
    k.sort()
    return k

Адаптировано из древнихФрагмент фрагмента кода ActiveState, о котором сам Алекс Мартелли написал несколько комментариев: http://code.activestate.com/recipes/52560/

Более короткий путь со списками:

def sort_uniq(alist):
   d = {}
   mod_list = [d.setdefault(i,i) for i in alist if i not in d]
   mod_list.sort()
   return mod_list

---

Помимо аккуратного Стивена (хотя и немного непривлекательного)один вкладыш, я думаю, это направлено на наименьшее количество строк и самый идиоматический способ сделать это с Python 2.2:

Благодаря Стивену Румбальски в комментариях, 2-я версия может быть сокращена с помощью функции zip Python:

def sort_uniq(alist):
   mod_list = dict(zip(alist,alist)).keys()
   mod_list.sort()
   return mod_list

Если бы list.sort() не работал по побочному эффекту, у нас был бы один вкладыш.;)

Answer 2

Idiomatic и в одну строку?Нет.

Вот не идиоматическая, безобразная, однорядная строчка.

>>> x = [4, 3, 3, 2, 4, 1]
>>> [y for y in (locals().__setitem__('d',{}) or x.sort() or x) 
        if y not in d and (d.__setitem__(y, None) or True)]
[1, 2, 3, 4]

Если приемлем простой двухслойный:

x = [4, 3, 3, 2, 4, 1]
x = dict(map(None,x,[])).keys()
x.sort()

Или сделайте двамаленькие вспомогательные функции (работают для любой последовательности):

def unique(it):
    return dict(map(None,it,[])).keys()

def sorted(it):
    alist = [item for item in it]
    alist.sort()
    return alist

print sorted(unique([4, 3, 3, 2, 4, 1]))

дает

[1, 2, 3, 4]

И, наконец, полифитонный вкладыш:

x = [4, 3, 3, 2, 4, 1]
x.sort() or [s for s, t in zip(x, x[1:] + [None]) if s != t]

Answer 3

Для записи, Python 2.2 имеет наборы, но в модуле "наборы", так что вы проделаете длинный путь:

from sets import Set
myList = list(Set(myList))
# now we're duplicate-free, a standard sorting might be enough
myList.sort()

Answer 4

Вероятно, лучший ответ - использовать двоичное дерево:

# Make yield work in Python 2.2
from __future__ import generators

class TreeNode(object):
    def __init__(self, value):
        self.left = None
        self.right = None
        self.value = value

    def add(self, value):
        if value == self.value:
            return
        if value < self.value:
            if self.left is None:
                self.left = TreeNode(value)
            else:
                self.left.add(value)
        else:
            if self.right is None:
                self.right = TreeNode(value)
            else:
                self.right.add(value)

    def __iter__(self):
        if self.left is not None:
            for value in self.left:
                yield value
        yield self.value
        if self.right is not None:
            for value in self.right:
                yield value

class DedupeSorter(object):
    def __init__(self):
        self.root = None

    def add(self, value):
        if self.root is None:
            self.root = TreeNode(value)
        else:
            self.root.add(value)

    def __iter__(self):
        if self.root is None:
            return []
        else:
            return self.root.__iter__()

def dedupe_and_sort(l):
    sorter = DedupeSorter()
    for value in l:
        sorter.add(value)
    return list(sorter)

Определенно не идиоматично, но должно быть быстрым.Он в основном создает древовидное множество и перебирает его.У меня нет Python 2.2, так что, надеюсь, он работает: p