All geek questions in one place

Best data structure to use in two sorted lists

I need a collection data structure that can do the following:

  • Sorting
  • Let me quickly infer the values ​​from the front and back of the list O (log n)
  • It remains sorted after entering a new value
  • Allow the user-defined comparison function, since I will store tuples and want to sort by a specific value
  • No thread protection required
  • It is not necessary to allow efficient searches ((I'm happy to keep a separate hash table for this)

My thoughts at this stage are that I need a priority queue and a hash table, although I don’t know if I can quickly set values ​​at both ends of the priority queue. Another possibility is to simply support the OrderedDictionary and sort the insert each time I add more data to it.

Since I'm interested in performance for a moderate number of elements (I would rate less than 200,000), I'm not sure what asymptotic performance I require for these operations. n will not grow indefinitely, so low constant productivity kin k * O(n)can be just as important O(n). However, I would prefer that both inserts and pop operations take O(log n)time.

Also, are there any specific implementations in Python? I really would like to avoid writing this code myself.

+3
source share
7 answers

You can get good performance for these operations using blisteither a database (e.g. sqlite , which is located in stdlib).

+2
source

I suggest some kind of balanced binary tree such as red-black tree.

A search in PyPi generates several implementations. A google search will give you more.

bintrees PyPi Python, C/Cython. , emptor.

- , (, , ) - O (log2 (N)), 200 000 17-18 .

+1

, , , ?

node, node ( " " ).

, ( min/max), / O (log n).

(// , -/, // ) O (logn) , .

, , python AVL ( ), : http://www.python.org/ftp/python/contrib-09-Dec-1999/DataStructures/avl.README

, .

+1

, , , - , .

, , O (1) min, max ( deleteMin deleteMax O (log (N))). , - Python, , .

, , :

http://www.mhhe.com/engcs/compsci/sahni/enrich/c9/interval.pdf

+1

O (log n) pop, dequeue insert, , - , , .

, , , , (1) (2) pop dequeue, , , . . , , , corr. .

-, min-max heap (. ), " ", , , . , O (n) .

min-max , min max O (1) , O (log (n)) min max, , .

+1

Java, TreeSet NavigableSet.

It is implemented as a Red-Black-Tree.

-1
source

Source: https://habr.com/ru/post/1745545/

More articles:


All Articles