Python: сортировать 2-кортеж иногда по первому, а иногда по второму элементу - PullRequest
Новая
       5

Python: сортировать 2-кортеж иногда по первому, а иногда по второму элементу

0 голосов
/ 29 августа 2018

У меня есть список кортежей целых чисел [(2,10), [...] (4,11),(3,9)]. Кортежи добавляются в список, а также регулярно удаляются из списка. Он будет содержать до ~ 5000 элементов.

В моем коде мне нужно использовать этот список, иногда отсортированный по первому, а иногда по второму элементу кортежа. Следовательно, порядок списка будет сильно меняться. Курорт может состояться в любое время.

Консервирование Pythons возможно только в том случае, если список уже сильно отсортирован. Так что этот общий подход частого обращения может быть неэффективным. Лучшим подходом было бы использовать две естественно отсортированные структуры данных, такие как SortedList . Но здесь мне потребуются два списка (один для первого элемента кортежа и один для второго), а также словарь для создания отображения вышеупомянутых кортежей.

Какой питонный способ решить эту проблему?

В Java я бы сделал это так: 

TreeSet<Integer> leftTupleEntry = new Treeset<Integer>();
TreeSet<Integer> rightTupleEntry = new Treeset<Integer>();
Hashmap<Integer, Integer> tupleMap = new HashMap<Integer,Integer>()

И имейте обе стратегии сортировки в лучшем классе сложности во время выполнения, а также необходимую связь между обоими числами.

  • Когда мне нужно отсортировать его по первому кортежу, мне нужен доступ ко всему списку (так как мне нужно вычислить совокупную сумму и другие операции)
  • Когда мне нужно отсортировать по второму элементу, меня интересуют только самые маленькие элементы, за которыми обычно следует удаление этих соответствующих кортежей.
  • Обычно после любого запроса запрашивается новый вид в соответствии с первым элементом.

Ответы [ 2 ]

0 голосов
/ 30 августа 2018

Что я сделал:

Я использую SortedKeyList и сортирую по первому элементу кортежа. Вставка в этот список O (log (n)). Чтение из него тоже O (log (n)). 

from operator import itemgetter
from sortedcontainers import SortedKeyList

self.list = SortedKeyList(key=itemgetter(0))
self.list.add((1,4))
self.list.add((2,6))

Когда мне нужно argmin в соответствии со вторым элементом кортежа, который я использовал 

np.argmin(self.list, axis=0)[0]

Что есть O (n). Не оптимально.

0 голосов
/ 29 августа 2018 
first_element_list = sorted([i[0] for i in list_tuple])
second_element_list = sorted([i[1] for i in list_tuple])
...