Разбить список на несколько списков, чтобы получить ускорение? - PullRequest
Новая
       11

Разбить список на несколько списков, чтобы получить ускорение?

3 голосов
/ 11 августа 2011

Допустим, мой список состоит из 1,000,000 записей. Для доступа к предмету время будет O(500,000), что мне кажется очень долгим.

Что происходит, когда я делю список на несколько списков? Давайте посмотрим на пример:
Разделив список на 10 частей, я бы получил следующий список: 

splitted_list = [
    [list with 100,000 entries],
    [list with 100,000 entries],
    [list with 100,000 entries],
    [list with 100,000 entries],
    [list with 100,000 entries],
    [list with 100,000 entries],
    [list with 100,000 entries],
    [list with 100,000 entries],
    [list with 100,000 entries],
    [list with 100,000 entries]
]

Время доступа к предмету будет O(5) + O(50,000) = O(50,005) и дает ускорение примерно на 1000%!

При разбиении исходного списка о его корне, который в данном случае равен 1000, получится список из 1000 списков, содержащий еще 1000 записей. 

splitted_list = [
    [list with 1000 entries],
    [list with 1000 entries],
    [list with 1000 entries],
    [list with 1000 entries],
    ...
]

Теперь взгляните на время доступа к предмету: 

O(500) + O(500) = O(1000)
O(1000) < O(50,005) < O(500,000)

Это оптимальная скорость примерно в 1000 раз! Думаю, невероятно верить, поэтому мой вопрос:

Это применимо и на практике, или это только теория?

Ответы [ 3 ]

5 голосов
/ 11 августа 2011

Получить элемент по индексу из списка равно O (1) независимо от размера списка.

4 голосов
/ 11 августа 2011

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

Ваша идея связана с различными структурами данных, из которых наиболее вероятным является список пропусков . Это структура данных, основанная на связанном списке, но с «магистралями» узлов, которые пропускают более одного элемента списка. Преимущество состоит в том, что вы можете бегать по шоссе, чтобы попасть в середину списка, а затем переходить на «более медленные полосы», когда вам нужна точность отдельных элементов, давая эффективность индексирования O (log n) - так же, как двоичное дерево . Конечно, недостатком является то, что более сложно (и медленнее) выполнять другие операции со связанным списком, такие как случайные вставки.

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

Вас может заинтересовать статья Википедии о структурах данных .

3 голосов
/ 11 августа 2011

Я предполагаю, что вы говорите о поиске элемента в списках.

Если вы говорите о разбиении отсортированного списка на множество отсортированных списков с указателями на их головы, поздравляю, вы почти обнаружили B-дерево.

Если эти списки действительно являются массивами (т. Е. У вас есть произвольный доступ с постоянным временем), вы также можете выполнить двоичный поиск.

...