LINUX.ORG.RU

Список сложных объектов или словарь из них же

 , ,


1

1

Это снова я. В предыдущих сериях темах упоминался класс для описания людей. Так вот, если я хочу насоздавать, допустим, пару тысяч его экземпляров с произвольными параметрами — во что удобнее их объединить? Можно в список — и ориентироваться по индексам, можно присвоить каждому уникальный ключ и собрать их в словарь.

С точки зрения объёма кода разница, вроде, невелика. Для внешнего пользователя тем более безразлично, потому что у всех экземпляров разные имена (значения self.name), и если кто-то захочет посмотреть сведения про Ивана Иванова, то будет искать его как раз по имени. Может быть, будет разница в скорости операций с этим самым списком или словарём?

Если тебе их хранить, то в БД, пусть СУБД занимается этим. А если обрабатывать, то в зависимости от того, по каким критериям и каким алгоритмом ты собрался это делать.

peregrine ★★★★★ ()
Последнее исправление: peregrine (всего исправлений: 1)
Ответ на: комментарий от peregrine

Да зачем БД, страсти какие :) Это всё будет создаваться каждый раз при запуске программы, а при выходе сбрасываться куда-нибудь по файлам. Наверное.

Что касается обработки. Ну, например, потом я пишу класс, который описывает место работы, в нём список employees = []. Потом выбираю из моих человечков тех, у кого occupation == 'unemployed', и забрасываю их в этот список работников. Потом каким-то образом меняются их параметры: увеличивается счётчик проработанного времени, например. В общем, ничего сверхъестественного.

al_exquemelin ★★★ ()
Ответ на: комментарий от al_exquemelin

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

Siado ★★★★★ ()
Ответ на: комментарий от al_exquemelin

Как раз БД идеальнно зайдет. Запрос на SQL и готово.

peregrine ★★★★★ ()
Ответ на: комментарий от Siado

Словарь медленный
Делай список

ничеси, с каких пор хэшмап медленнее связного списка

Dred ★★★★★ ()
Ответ на: комментарий от al_exquemelin

сбрасываться куда-нибудь по файлам

не проще ли отдать все это двишку БД и не париться о записи/поиске ? Можно какую-нибудь embeded db поискать чтобы не заморачиываться с сервером

Dred ★★★★★ ()
Ответ на: комментарий от al_exquemelin

https://docs.python.org/3/library/sqlite3.html

ничего не нужно устанавливать, вся бд в одном файле, мгновенный полнотекстовый поиск, реляционная модель, sql, транзакционность. для инспектирования можно использовать консольную утилиту sqlite. одни плюсы, короче.

anonymous ()

Может быть использовать для этих целей множество? Зачем плодить дополнительные индексы? Ну это так - предположение. А вообще БД в данном случае конечно поинтереснее выглядит

saibogo ★★ ()
Ответ на: комментарий от Dred

С каких пор тип «список» в Python стал связным списком?

Virtuos86 ★★★★★ ()

если кто-то захочет посмотреть сведения про Ивана Иванова, то будет искать его как раз по имени

значит, словарь

только отделу кадров скажи, чтоб не нанимали никого с одинаковыми ФИО

MyTrooName ★★★★★ ()
Ответ на: комментарий от Dred

ничеси, с каких пор хэшмап медленнее связного списка

в питоне List - это вектор

MyTrooName ★★★★★ ()

Сделай отдельный класс-контейнер с методами лукапа по нужным тебе параметрам. (Лучше конечно отдельные классы лукапа, свой для каждого нужного параметра, но ты же будешь плакать, что слишкам сложна). Внутри словарь id -> объект. Если нужно ускорить лукап по какому то параметру, строй хэш параметр -> id.

no-such-file ★★★★★ ()
Последнее исправление: no-such-file (всего исправлений: 1)
Ответ на: комментарий от Dred

ничеси, с каких пор хэшмап медленнее связного списка

Хотя бы с таких, что хешмап это надстройка над связанным списком

Siado ★★★★★ ()
Ответ на: комментарий от Siado

ЕМНИП в питоне как раз таки стандартный хэшмап с O(1). Поиск по списку будет O(n)

Dred ★★★★★ ()
Ответ на: комментарий от MyTrooName

мой косяк, искать по списку все равно O(n)

Dred ★★★★★ ()
Ответ на: комментарий от Siado

За нахождение алгоритма поиска по списку, который будет быстрее поиска по хешмапу тебе нобелевка светит.

irr123 ()
Ответ на: комментарий от RazrFalcon

Массивы же умеют. Хэшмапы аналогично работают

Dred ★★★★★ ()
Ответ на: комментарий от RazrFalcon

нотация О(1) не значит, что поиск по хешмапе происходит за секунду, это значит что поиск всегда происходит за константное время, а

О(n) значит все время прямопропорционально количеству элементов, среди которых происходит поиск (на самом деле, по списку можно искать со сложностью O(ln(n))).

Если совсем заморочиться и взять конкретную реализацию питонячего дикта и листа, то поиск в маленьком листе действительно будет быстрее поиска в маленьком дикте, потому что до какого-то конкретнго n, ln(n) будет меньше чем константное время поиска в дикте.

irr123 ()

По сабжу:

решение для продакшена - однозначно БД,

решение для себя - что угодно, список, хешмап, дерево. Разница между этими структурами данных в сложности поиска, вставки/добавления/удаления, поэтому что выбрать тебе в данном конкретном случае зависит от того, как ты будешь этими данными оперировать.

irr123 ()

Про LDAP не слышали? Иерархический способ хранения информации о реальном мире, в т.ч. и о людях. Тем более если в дальнейшем речь пойдёт о группах и ролях - LDAP идеально подойдёт.

и если кто-то захочет посмотреть сведения про Ивана Иванова

Полагаться на уникальность и низменность имени и фамилии - очень, крайне дурная затея.

DRVTiny ★★★★★ ()
Ответ на: комментарий от irr123

За нахождение алгоритма поиска по списку, который будет быстрее поиска по хешмапу тебе нобелевка светит.

Поиска чего? Если ты считаешь убербыстрым поиск конкретного элемента по конкретному имени удачным - может в каких-то кейсах так оно и будет. Но с тем же успехом что мешает хранить индекс конкретного элемента?

Попробуй поищи в хешмапе по регекспу =)

З.ы.

Хешмап - это вообще не для поиска. Это способ вместо числового индекса сделать индекс символьный или еще какой извращенный, путем усложнения кода.

Siado ★★★★★ ()
Последнее исправление: Siado (всего исправлений: 1)
Ответ на: комментарий от irr123

Если совсем заморочиться и взять конкретную реализацию питонячего дикта и листа, то поиск в маленьком листе действительно будет быстрее поиска в маленьком дикте, потому что до какого-то конкретнго n, ln(n) будет меньше чем константное время поиска в дикте.

Подобные рассуждения как раз и демонстрируют сущность «алгоритмической сложности» примерно как «чушь собачья».

А если n^3 циклов отнимает в 1000 раз меньше времени, чем n других циклов? А если использование алгоритма в n*log(n) циклов влечёт за собой перерасход рабочего времени в N раз относительно сроков сдачи проекта? Или что такое константная сложность в сравнении с N? Если они вообще несравнимы - зачем сравнивать? Никому не нужны магические N и степени с логарифмами. Нужны конкретные показатели: среднее время отклика на запрос (возможно, никому не нужно тратить в 3 раза больше времени, чтобы время отклика стало в 100 раз меньше, если оно итак всех устраивает), стоимость и длительность разработки. Все эти выкладки про N - это сказка о «прочих равных условиях», а они, внезапно, никогда равными не бывают, особенно если речь идёт о такой крайне скользкой вещи, как интерпретируемый ЯП.

DRVTiny ★★★★★ ()
Ответ на: комментарий от irr123

При чём тут секунды? Речь о том, что хешмап O(1) - в лучшем случае. И также зависит от реализации.

Реальный O(1) только у вектора.

RazrFalcon ★★★★★ ()
Ответ на: комментарий от DRVTiny

Если вы не понимаете, что такое алгоритмической сложности - это не значит, что она не нужна.

RazrFalcon ★★★★★ ()
Ответ на: комментарий от RazrFalcon

Нет, такое в общем случае невозможно: количество коллизий напрямую зависит от количества элементов, каждая разрешённая коллизия поиска отнимает больше времени, поскольку в простейшем случае предполагает тупой перебор небольшого списка элементов, значение хеш-функции для которых совпало. Идеальных хеш-функций, у которых не бывает коллизий - нет. Вернее, есть такая - это представление ключа как набора байт, составляющего целое число и размещение типа+ссылки значения в соотв. индексе вектора. Правда для такого чудо-вектора не хватит всей когда-либо произведённой памяти.

DRVTiny ★★★★★ ()
Ответ на: комментарий от Dred

Примитивные - да. В сложных у нас есть buckets, rehash и разрешение конфликтов.

RazrFalcon ★★★★★ ()
Ответ на: комментарий от DRVTiny

Я об этом же.

Но perfect hash всё равно есть, но для заранее известных данных.

RazrFalcon ★★★★★ ()
Ответ на: комментарий от RazrFalcon

А если я понимаю, что это такое и знаю, что это чушь собачья, придуманная макаками для других макак с целью меряния органами?

Я предельно конкретно объяснил, почему O - бред чистой воды. Если вам сказать нечего - не говорите.

DRVTiny ★★★★★ ()
Ответ на: комментарий от RazrFalcon

Для заранее известных данных хеш - это тупо более удобное для несовершенного хомо «текстовое» представление индексов обычного вектора. В программах на Си так очень часто и делают: объявляют константы с «говорящими» именами для обычных индексов.

DRVTiny ★★★★★ ()
Ответ на: комментарий от RazrFalcon

Реальный O(1) только у вектора.

Да, только при этом если соотв участок памяти не лежит к кеше процессора ральное врем обращения к разным участкам вектора может быть разным. Мало того, нельзя исключать ситуацию, когда кусок вектора окажется в странице памяти, сброшенной на диск: ОС в общем-то пофигу, что вы храните в памяти и как далеко оно простирается. Не обращался в страницу N проходов свопера - всё, при настроенной агрессивной политике свопинга уедет страница на диск.

DRVTiny ★★★★★ ()
Ответ на: комментарий от DRVTiny

O, как минимум, позволяет прогнозировать производительность.

А ваше «среднее время отклика на запрос» будет зависит от чего угодно, в том числе и от фазы луны.

RazrFalcon ★★★★★ ()
Ответ на: комментарий от RazrFalcon

Я о том, что для заранее известного набра ключей можно без всяких автоматизированных функций набить соответствие «ТЕКСТ» = Индекс.

Кстати, это явно быстрее использования функций в рантайме.

DRVTiny ★★★★★ ()
Последнее исправление: DRVTiny (всего исправлений: 1)
Ответ на: комментарий от DRVTiny

Зачем что-то набивать, если уже есть готовые инструменты для phf?

RazrFalcon ★★★★★ ()
Последнее исправление: RazrFalcon (всего исправлений: 1)
Ответ на: комментарий от Siado

Поиска чего?

Задача(в контексте треда): нужно найти объект person, name у которого «вася». У тебя есть структуры из объектов(условно пишу сами объекты как дикты):

[
{name: толя},
{name: коля},
{name: вася}
]

{
толя: {name: толя},
коля: {name: коля},
вася: {name: вася}
}

Где происк будет проще?

З.ы.

Ты интерпретируешь хэшмап как список/массив с символьным индексом, и оно так и есть с одной стороны, но с другой, хешмап можно использовать как структуру для поиска за константное время.

irr123 ()
Ответ на: комментарий от RazrFalcon

Я же привёл пример с N^3 циклами, выполняющимися в 1000 раз медленнее, чем N циклов. Что-так не бывает? А я думаю - вполне бывает. Безусловно, это при определённом N, дальше при каком-то куда большем N оба варианта сравнятся, а при N, стремящемся в бесконечность вариант с N циклов конечно победит.

Но это теоретизация. А бизнесу нужны вполне определённые N и вполне определённое время отклика. Как и разумная стоимость человеко-часа, как и разумные сроки разработки. Программирование - это либо в основном коммерческая деятельность, либо в основном наука. За первую платят, за вторую - тоже платят, но не у нас.

DRVTiny ★★★★★ ()

Ну ничего себе вы тут нафлудили, пока меня не было. Даже не знаю теперь, что и кому отвечать в первую очередь.

saibogo

использовать для этих целей множество

Множество — это же список неповторяющихся элементов, не? Надо подумать, в чём будет отличие со стороны кода.

MyTrooName, DRVTiny

По поводу имени-фамилии. Я своих человечков специально генерирую такими, чтобы это сочетание не повторялось. Если начнут появляться тёзки-однофамильцы, значит, в генераторе имён ерунду написал.

no-such-file

Сделай отдельный класс-контейнер с методами лукапа по нужным тебе параметрам.

То есть класс для совокупности человечков? Мысль, конечно. Хотя я тут думал обойтись опять же либо списками, либо словарями, если нужно, например, раздавать им должности: {'должность': <объект Иван Иванов>, 'должность': <объект Иван Петров>}.

irr123

Разница между этими структурами данных в сложности поиска, вставки/добавления/удаления

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

al_exquemelin ★★★ ()
Ответ на: комментарий от DRVTiny

Проблема подобных рассуждений в том, что это рассуждения словами вместо однозначного графика с прямой, параллельной одной из координатных осей и графика линейной зависимости/логарифма. На этом графике очевидно было бы видно, где один алгоритм работает быстрее, где также, а где обгоняет.

В математическом подходе нет ничего скользкого и неоднозначного.

irr123 ()
Ответ на: комментарий от DRVTiny

Так можно дойти до того, что прога тормозит из-за того, что кто-то параллельно генту собирает. И кто в этом виноват? Автор проги?

RazrFalcon ★★★★★ ()
Ответ на: комментарий от RazrFalcon

O(1) у хешмапа в среднем. Статистику портит как раз обработка коллизий (о которой вы вроде ниже уже начинали спорить).

irr123 ()
Ответ на: комментарий от irr123

В матиматике не силён, но почему они называют O(1) средним? Чтобы быть средним, должен быть результат лучше O(1), но такого не бывает.

RazrFalcon ★★★★★ ()
Ответ на: комментарий от RazrFalcon

Если в кратце, то

должен быть результат лучше O(1)

необязательно, как пишут, для «хороших» хеш-функций частота коллизий стремится к нулю, поэтому в хеш-мапе, построенной на такой функции отклонение от лучшего значения тоже стремится к нулю, так и получают среднее. По-моему в этой лекции про хеш-функции, хешмапы и их сложность Бабичев рассказывает https://sphere.mail.ru/materials/video/313/ , плюс делает анализ нескольких хеш-функций и показывает распределения вероятностей коллизий.

irr123 ()
Ответ на: комментарий от irr123

В Ваших рассуждениях есть тоже некоторая неоднозначность: ибо чтобы хотя бы аппроксимировать этот ваш чудесный график, нужно в общем-то проводить измерения (бенчмарки). Ну и конечно реального кода, а не абстрактных циклов в полном вакууме.

DRVTiny ★★★★★ ()
Ответ на: комментарий от RazrFalcon

Суть в том, что любые абстракции должны разумно использоваться только до определённого момента. Возможно, за разные уровни абстракции должны отвечать разные люди, но, поверьте, бизнесу не особо интересно нанимать системного аналитика, системного архитектора, специалиста по ОСям, специалиста по железу, специалиста по БД - как правило, все хотят нанять этакий комбайн, понимающий хотя бы, как всё взаимосвязано.

Поэтому ну да, если вы проектируете приложение, использующее один размазанный на 4Гб вектор (по нынешним временам не больно большая структура данных) и при этом не знаете о том, что при неверных настройках его кусок может улететь в своп, а это в свою очередь при немного легкомысленно написанном коде может привести к ситуации гонки (вы-то думали, что «ничего страшного, это всего лишь чтение 64-х битного целого», а попали в ситуацию, когда процесс был заблокирован по вводу-выводу и какой-то другой его параллельный собрат получил в это время управление и, возможно, даже раньше вашего считал подкачанную страницу) - можете запросто столкнуться с ситуацией, когда «оно эпизодически выдаёт стек-трейс, ХЗ вообще от чего».

Ну т.е. нужно всё-таки либо выдвигать какие-то требования к окружению, в котором работает приложение, либо это окружение предоставлять, иногда вплоть до железа.

DRVTiny ★★★★★ ()
Последнее исправление: DRVTiny (всего исправлений: 1)
Ответ на: комментарий от DRVTiny

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

Я никогда не интересовался и не искал (поэтому не знаю) бенчмарков, где бы сравнивали производительность/скорость работы например quick-sort и сортировку пузырьком или алгоритм линейного поиска по списку и поиск по хеш-мапе в зависимости от количества элементов.

Почему? Потому что в простых случаях сложность алгоритма кажется очевидной после прочтения/понимания алгоритма, в сложных случаях приходится читать разъяснения. Нотации О/Θ(n) придумали чтобы абстрагировать такое интуитивное понимание и ввести какую-то метрику для сравнения алгоритмов между собой. Это понятие сложности не гарантирует каких-то реальных цифр на железе, оно для того чтобы сравнивать абстрактные алгоритмы друг с другом.

А верить или не верить в мат.доказательства - личное дело каждого.

надеюсь, что ответил на пост

irr123 ()
Ответ на: комментарий от al_exquemelin

То есть класс для совокупности человечков?

Да. Помимо прочего он будет выполнять и функции сохранения/восстановления данных. В общем, тебе нужен EntityManager.

no-such-file ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.