Почему вставляет посреди связанного списка O (1)?
Я думаю, что это может сработать для вас.
import requests
import csv
from collections import defaultdict
STATE = 'ca'
YEAR = 2017
def split_data_to_csv(state, year):
data = defaultdict(list)
headers = None
r = requests.get('http://date.nager.at/api/v1/get/{}/{}'.format(state, year))
if r.status_code == 200:
entries = r.json()
for entry in entries:
month = entry['date'].split('-')[1]
data[month].append(entry.values())
if not headers:
headers = entry.keys()
for month, entries in data.items():
with open('out_{}.csv'.format(month), 'wb') as out:
writer = csv.writer(out)
writer.writerow(headers)
writer.writerows(entries)
split_data_to_csv(STATE, YEAR)
14 ответов
Вы правы, в статье «Индексирование» рассматривается как отдельная операция. Таким образом, вставка сама по себе составляет O (1), но добраться до этого среднего узла - O (n).
Вставка в связанный список отличается от итерации по нему. Вы не обнаруживаете элемент, вы сбрасываете указатели, чтобы поместить элемент туда. Не имеет значения, будет ли он вставлен рядом с интерфейсом или ближе к концу, вставка по-прежнему включает переназначение указателей. Конечно, это будет зависеть от того, как это было реализовано, но в этом сила списков - вы можете легко вставлять их. Доступ через индекс - это то место, где сияет массив. Для списка, однако, поиск n-го элемента обычно занимает O (n). По крайней мере, это то, что я помню из школы.
Нет, когда вы решаете, что хотите вставить, предполагается, что вы уже находитесь в середине итерации по списку.
Операции со связанными списками часто выполняются таким образом, что на самом деле они не рассматриваются как общий «список», а как набор узлов - подумайте о самом узле как о итераторе для вашего основного цикла. Просматривая список, вы в рамках своей бизнес-логики замечаете, что необходимо добавить новый узел (или удалить старый), и вы это делаете. Вы можете добавить 50 узлов за одну итерацию, и каждый из этих узлов - это всего лишь O (1) время, чтобы разъединить два соседних узла и вставить новый.
Редактировать: Человек, вы вводите второй абзац и все внезапно вместо того, чтобы быть первым, кто откликнулся, вы пятый и говорите то же, что и первые четверо!
Для сравнения с массивом, а это то, что На диаграмме показано, что это O (1), потому что вам не нужно перемещать все элементы после нового узла.
Итак, да, они предполагают, что у вас уже есть указатель на этот узел или что получение указателя тривиально. Другими словами, проблема формулируется: « данный узел в X , какой код вставить после этого узла?» Вы можете начать с точки вставки.
Потому что это не связано с каким-либо циклом.
Вставка похожа:
- вставить элемент
- ссылка на предыдущий
- ссылка на следующий
- сделано
это в любом случае является постоянным временем.
Следовательно, вставка n элементов один за другим составляет O (n).
Вставка выполняется за O (1), если вы знаете, куда вы собираетесь ее поместить.
Разве этот анализ не учитывает обнаружение операции узла (хотя она и требуется) и только саму вставку?
Вы поняли. Вставка в заданной точке предполагает, что у вас уже есть указатель на элемент, который вы хотите вставить после:
InsertItem(item * newItem, item * afterItem)
Нет, поиск не учитывается. Но если у вас уже есть указатель на элемент в середине списка, вставка в этой точке будет O (1).
Если вам нужно его найти, вам придется добавить время для поиск, который должен быть O (n).
Статья посвящена сравнению массивов со списками. Поиск позиции вставки для массивов и списков осуществляется за O (N), поэтому в статье это игнорируется.
O (1) зависит от того факта, что у вас есть элемент, в который вы вставите новый элемент. (до или после). Если вы этого не сделаете, это O (n), потому что вы должны найти этот предмет.
Я думаю, что это просто случай того, что вы выбираете для обозначения O (). В случае вставки обычной операцией подсчета является операция копирования. В случае с массивом вставка в середину включает в себя копирование всего, что находится выше этого места, в память. В связанном списке это становится установкой двух указателей. Вам нужно найти место, что бы вы ни вставили.
Наиболее распространенными случаями, вероятно, является вставка в начале или в конце списка (и на поиск концов списка может не потребоваться время).
Сравните это с вставкой элементов в начале или в конце массива (что требует изменения размера массива, если он находится в конце, или изменения размера и перемещения всех элементов, если он находится в начале).
Я тоже некоторое время назад искал это. Я наткнулся на HTMLDOC http://www.easysw.com/htmldoc/ , бесплатное приложение командной строки с открытым исходным кодом, которое принимает HTML-файл в качестве аргумента и выводит из него PDF-файл. У меня это неплохо сработало для моего побочного проекта, но все зависит от того, что вам действительно нужно.
Компания, которая его производит, продает скомпилированные двоичные файлы, но вы можете бесплатно загрузить и скомпилировать из исходного кода и использовать его бесплатно. Мне удалось скомпилировать довольно недавнюю ревизию (для версии 1.9), и я намерен выпустить для нее двоичный установщик через несколько дней, поэтому, если вам интересно, я могу предоставить ссылку на нее, как только я ее опубликую.
Редактировать (25.02.2014): Похоже, что документы и сайт перемещены на http://www.msweet.org/projects. Для массива это все еще O (n), поскольку вам нужно переместить все последовательные узлы.