LINUX.ORG.RU

Структуры данных на C

 , , , ,


1

2

А вы пишете свои структуры данных? Мне тут один парень вчера на ютубе затирал то, что это полезный навык. Мол, ему приходилось писать свой двусвязный список, когда он что-то там кодил на C под контроллеры. Я ему на это сказал, что это порочная практика, потому что нужно брать готовый код, написанный более умными людьми и проверенный сто раз другими. Потому что будь ты хоть семи пядей во лбу, всё равно нафигачишь ошибок. Да и время просто тратишь впустую — вместо того, чтобы решать необходимую задачу, ты придумываешь себе интересные подзадачки и упарываешься по ним. Мне кажется, что это даже такой способ прокрастинации, когда не хочется решать основную проблему, то можно возбудить в себе NIH-синдром и начать переписывать то, что уже и без тебя существует.

Короче, вопрос темы я уже задал, но повторюсь: как часто приходится, и вообще приходится ли вам писать вот это всё? Структуры данных, алгоритмы для работы с ними, может даже фреймворки какие-то? И, если да, почему не считаете, что вы страдаете фигнёй?

Поразмыслив ещё немного, я решил убить пару часов времени и написать тот злосчастный двусвязный список на C. К языку этому я не прикасался уже лет дцать, да и вообще не знаю, как в нём принято кошерно такие вещи пилить, но решил нафигачить никуда не подглядывая чисто по памяти. Вот, что из этого вышло: https://github.com/NightmareZ/plain-c-data-structures Можно ещё добавить очередь, деревья всякие, хэшмапы и прочее-прочее, но чёт мне кажется, что я уже забил на эту затею и не буду этого делать, а лучше поиграюся во что-нибудь сегодня. А вы когда-нибудь реализовывали хэшмапу? И, если да, то нафига?

Ответ на: комментарий от dimgel

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

LINUX-ORG-RU ★★★★★
()
Ответ на: комментарий от LINUX-ORG-RU

Да, прикольно. Хотя наверное это кому как. Я всегда хотел заниматься такими вот вещами – низкоуровневыми, байтодрочерскими, CS-ными. Но не сложилось, а теперь уж поздно.

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

Пока что 15 минут смотрю, ну пока он очевидности втирает, но с верным посылом.

Я всегда хотел заниматься такими вот вещами – низкоуровневыми, байтодрочерскими

Так занимайся кто мешает то?

Но не сложилось, а теперь уж поздно.

Ой да лаааааадно. Я то бывает сижу неделями ковыряюсь с какойнить фигнёй. А я ваще никогда программистом не был. Да и беды с башкой. А тут мид плюсовик, а сиську просишь :D

Взял и начал. Ну правда надо во что-то упереться с начала =) Но я не верю что у тебя где то нет тормознуче лагучей фигни которую можно забайтодрочить. Продумав от и до что куда, зачем и почему.

LINUX-ORG-RU ★★★★★
()
Ответ на: комментарий от dimgel

Мужик двигает прогресс. Тут как с фундаментальной наукой: копошатся-копошатся – а потом ррраз! и выстрелило

Что «выстрелило»? На 10% повысилась производительность и снизилось потребление памяти? Хэш-таблица — это случайно-оптимальный способ организации ассоциативного массива для конкретной архитектуры процессора.

Случайно — потому что возможно подобрать набор данных, который положит хэш-таблицу так, что она станет хуже связанного списка с полным перебором поиска O(N). Примерно как с Quicksort, который на специально сформированных массивах данных дает stack overflow — если учитывать этот недостаток, то у него не может быть масштабируемости O(N*logN).

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

Для конкретной архитектуры процессора — потому что ориентирован на конкретную модель работы с памятью, то есть медленное чтение данных из оперативы кэш-линиями — отсюда ориентация на «уместить данные одного запроса в минимум кэш линий». Он даже умудрился привязаться к SSE2. Но он в жизни не сможет свой хэш натянуть на GPGPU, которая организована иначе. где канал оперативы и шире, и быстрее, но при этом возникает необходимости выполнять сразу несколько операций за раз. На FPGA оно уже совсем никак не налазит, потому что там уже нет никаких кэш-линий.

Ну и последний гвоздь в крышку гроба: хэш-таблица — это фундаментально однопоточный-однопользовательский алгоритм. А сейчас у нас актуальна какая проблема? Много ядер и нельзя их использовать. А чтобы их использоваться, нужно применять многоверсионную структуру данных, нужно распределять данные не по случайному хэшу, а «подобное к подобному», а отсюда ключем должна быть строка или другая семантическая единица, и тогда его безликий хэш оказывается в пролете. То есть, его презентация устарела еще до того, как вышла в публику.

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

«все плоды творчества этого чела», подозреваю, ни тебе, ни мне неизвестны

Может быть там есть здоровые склонности, но в данном случае я отвечаю не ему, а тебе. Ты восхищаешься его лекцией, а я, например, нет — и я пояснил почему. Я мог бы сделать хэши не хуже, но только за очень хорошие деньги — иначе смысла в этом нет. А «смысл» — это ускорить работу уже имеющегося в гугле кода, который в большинстве своем написан «на отлюбись» и его не хотят переписывать. Ускорять работу устаревшего говна — это совсем не «двигать прогресс». Я согласен с тем, что одними увольнениями много не наоптимизируешь, но как минимум так можно сократить количество устаревшего софта, который прямо сейчас, в 2021, плодится угрожающими темпами, он устарел еще до того, как был написан, потому что ум программистов прочно застрял где-то в 80-90-х, и уже монорепа гугла перевалила за два миллиарда строк.

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

Но не сложилось, а теперь уж поздно.

Дружище, не поздно!
Желаю тебе разрушить высокий забор, который сам перед собой воздвиг …

В сфере IT БЕЗДНА нерешенных или решенных плохо задач.

К примеру ВЫСОКИЕ УМЫ пятьдесят лет не могут придумать новой технологии разработки компиляторов, доступа к данным, …, …

А причина то в чем?

1) ЛЕНЬ.  
2) Не нужно.
3) ЛЕНЬ.
4) ЛЕНЬ.
...

Тех кто создает новое единицы.
И не потому, что они лучшие, а потому что

НЕ ЛЕНЯТСЯ

Так что постарайся побороть свою ЛЕНЬ. И все будет

Ok!
anonymous
()
Ответ на: комментарий от anonymous

К примеру ВЫСОКИЕ УМЫ пятьдесят лет не могут придумать новой технологии разработки компиляторов, доступа к данным, …, …
А причина то в чем?
1) ЛЕНЬ.
2) Не нужно.
3) ЛЕНЬ.
4) ЛЕНЬ.
Тех кто создает новое единицы

А теперь попробуй взять свои аргументы и при помощи них ответить: почему x86 до сих пор является лидирующей архитектурой процессоров? Учитывая то, что сам Intel разрабатывал i960. Лень? Не нужно? Единицы создают новое? По итогу вся твоя мотивация сводится к «just do it» и «начни с себя». А я предлагаю другую мотивацию: новая технология разработки компиляторов никому не нужна. потому crypt ничего не потерял, когда не вкатился в эту нишу. Единственная его настоящая проблема заключается в том, что он жалеет о том, что когда-то не вкатился в эту нишу.

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

А я предлагаю другую мотивацию: новая технология разработки компиляторов никому не нужна. потому crypt ничего не потерял, когда не вкатился в эту нишу.

Старая песня.
Все ленивые ее всегда поют и танцуют с бубном, если нужно что-то разработать новое …
Еще популярно суждение

До нас все украли
anonymous
()

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

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

Еще популярно суждение До нас все украли

Раньше бывало в форумах новички фантазировали и предлагали иногда интересные пути решения задач.
Их конечно шельмовали, выливали на них ЦИСТЕРНУ ГОВНА и

Банили

Ныне многие и рот боятся открыть и сказать

Ребята, а может быть можно эту задачу решить вот так?

Причина боязни

ЦИСТЕРНА ПАХУЧЕГО ШОКОЛАДА
anonymous
()
Ответ на: комментарий от anonymous

А деньги на школьные обеды мама даёт?

Свои 400к имею, на обеды хватает.

Да вы все тут миллионеры, я забыл совсем. Некоторые даже долларовые.

vihoco3039
() автор топика
Ответ на: комментарий от anonymous

Банили

И продолжают. И будут продолжать. Цензура на форумах, в том числе технических, похлеще цензуры в тоталитарных государствах. Плюс синдром вахтёра у каждого первого модератора.

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