Здравствуйте, Ватакуси, Вы писали:

В>С хешем, без деревьев.

С хешем не так сложно, я, скорее, с баллансировкой дерева не справлюсь.

Здравствуйте, TMU_1, Вы писали:

TMU>А как же ты работаешь??

Зажмуриваюсь и по клавиатуре херачу, как же еще?

А ты сбалансированные деревья по памяти пишешь? Уважаю!

Здравствуйте, sergey2b, Вы писали:
S>Проффесор поделитесь пожалуйста вопросами которые вы сейчас даете по алгоритмам и С++
Вот топ-10 вопросов, которые профессора сейчас дают по алгоритмам и C++
1. Мой экран всем видно?
2. Что значит "котик"?
3. Кто-нибудь знает, как в этой зуме со второго монитора трансляцию настроить?
4. У всех мой емейл есть, или кто-то опять будет рассказывать что отправил ответы мне в воцап?
5. То, что защит дипломов в этом году не будет, уже всем понятно, или вам надо ещё раз ссылку на выступление ректора дать?
6. У кого там микрофон включен и ребёнок меня перекрикивает?
7. А как вы себе представляете запрет на списывание во время онлайн-экзамена?
8. Наташа, я через десять минут заканчиваю с этими дебилами, ты суп поставила греть?
9. А что, микрофон не отключается, когда я камеру отключаю?
10. И когда, ***, всё это кончится уже?

Здравствуйте, Ватакуси, Вы писали:

В>Правда не сложно?
В>https://github.com/python/cpython/blob/master/Objects/dictobject.c

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

Здравствуйте, LaptevVV, Вы писали:

LVV>Это если доходить до слова посимвольно.
Не обязательно посимвольно, скорее попрефиксно, до точки где начинается разветвление.

LVV>А если слово целиком без поиска посимвольно — то лучше хеша ничего нет.
Ну он ж хочет чтоб было с префиксным поиском.

KP>Если взять из STL вектор, список да хеш, то это дело не очень хитрое, хотя с корректной поддержкой exception-safity, move-semantic и прочим может выйти ой
KP>А вот деревья точно не напишу,



А как же ты работаешь??

Здравствуйте, Ватакуси, Вы писали:

В>С хешем, без деревьев.

и поместить весь английский или русский словари в 64к ROM + на манимупляцию с ним еще 64к РАМ

задача абсолютно реальная для электроных пишуших машинок
я поучаствовал в ее решении в 89 году на z80

LVV>>Хеш-функция — это вычисление значения многочлена от строки, так что никаких О(длина строки тут нет).
E>Это как так? Ты хочешь сказать, что от строки в 10 букв и в 10 мегабайт хэш за одинаковое время считается?
Ты в словаре слова видел? Они по 10 метров?
E>Кроме того, ещё в хэш-таблице, в конце, надо сравнивать строку со строкой, при наличии коллизий, неоднократно. Это тоже пропорционально длине строки. Так что хэш-таблица строк, по добавлению это никак не меньше O(размер добавляемого текста)? а по поиску никак не меньше O(объём текста, который ищем).
Коллизии разными способами решаются, не только последовательным рехешированием.
Ну, и как всякая вероятностная система, сильно зависит от распределения.
Далее надо учитывать специфику словаря — универсальный всемогутер нам нафиг не нужен.
E>Очевидно бор в этом смысле не хуже, а если не жаль памяти, то и лучше
Может быть.
E>Ну это да, но если самому писать конкуренты STL-контейнерам, трудно адекватные контексты использования перебрать.
E>С другой стороны в конкретном случае словаря из строк в что угодно, логичнее написать самом бор и сравнить с STL-ной мапой и хэш-мапой (которая беспорядочная)
Ну, время будет — попробую.

S>На вопрос так и не ответили Т.е. это были забугорные конторы? Находили по резюме или рекомендациям? Резюме на SO было?
Подозреваю, что забугорные. Говорю же, тайна покрытая мраком.
Резюме с линкеда они находили.

Здравствуйте, sergey2b, Вы писали:

S>с функцией отображения слов начинающихся с уже введенных символов
Для такого будет удобнее какой нить вариант radix tree, например patricia trie, но не hash как ты просишь.

LVV>>А если слово целиком без поиска посимвольно — то лучше хеша ничего нет.
CC>Ну он ж хочет чтоб было с префиксным поиском.
Где? У него написано с хешем без деревьев

Здравствуйте, LaptevVV, Вы писали:

LVV>Где? У него написано с хешем без деревьев

А, пардон, про "с функцией отображения слов начинающихся с уже введенных символов" это sergey2b добавил тут: Re[2]: А вы без подготовки сможете свой словарь написать?

Автор: sergey2b
Дата: 24.01.20

LVV>>На С++ — без вопросов.
В>И разрешение коллизий? По памяти?
Ну, а какие проблемы-то?
У меня позавчера был экзамен как раз по алгоритмам.
Дык мне студенты все рассказали: и про хеши, и про коллизии...

Здравствуйте, Ватакуси, Вы писали:

В>С хешем, без деревьев.

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

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

Здравствуйте, sergey2b, Вы писали:

S>нет, средний словарь 10 тыс слов, среднее слово 5 символов, у вас только на поинтеры уйдет 20к и 60к на хранение оригинальных слов, а памяти 64 ну или 128к
Я видел в свое время реализацию трая без всяких поинтеров, очень компактно, там как раз препод рассказывал о том, как можно умудриться уместить весь словарь в килобайты памяти. На ютубе есть, лекции по алгоритмам толь MIT, толь Беркли. Скорее МИТ, там еще препод молодой, явно потомок российских эмигрантов, с длинными волосами и лысиной, и это одна из последних лекций. Он там начал именно с классического трая и затем показал как его хорошо можно упаковать.

LVV>>>На С++ — без вопросов.
В>>И разрешение коллизий? По памяти?
LVV>Ну, а какие проблемы-то?
LVV>У меня позавчера был экзамен как раз по алгоритмам.
LVV>Дык мне студенты все рассказали: и про хеши, и про коллизии...
LVV>
Так это они рассказали. А ты написать сможешь?-)

Здравствуйте, Ватакуси, Вы писали:

В>С хешем, без деревьев.

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

Здравствуйте, LaptevVV, Вы писали:

LVV>>>А если слово целиком без поиска посимвольно — то лучше хеша ничего нет.
E>>А что тут означает слово "лучше"? Лучше по какому критерию?
LVV>Хеш = О(1)

Эмм, но это ведь только в среднем, для большого количества элементов. И не забывайте, что строку ключа придется просканировать от начала до конца, чтобы посчитать её хэш. В реальных сценариях может оказаться, что упорядоченный std::map с небольшим количеством элементов будет не хуже unordered_map с его теоретическим O(1). И оба эти {unordered_}map могут проиграть линейному поиску в массиве с небольшим количеством элементов, которому современные процессоры отлично сделают prefetch памяти в кэш.

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

Здравствуйте, LaptevVV, Вы писали:

PM>>Хорошо, что вы рассказываете студентам про O(1), но стоит сказать и про разные константы такой сложности. И вообще, как всё в современных системах сложно
LVV>Это все понятно. Я им рассказываю даже случаи из моей практики.
...
LVV>Дня через 2 один пацан пишет — проблема в реализации дека в Студии.
LVV>Хреново реализована работа с памятью.
LVV>Порекомендовали переделать под вектор (о чем я уже и сам подумывал).
LVV>Естественно, после рефакторинга под вектор все встало на свои места: разница во времени примерно 10-12% в пользу gcc.
LVV>Так что мы не голой теорией занимаемся.

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

Хороший пример, почему стоит начинать выбор линейного контейнера с std::vector и в 99,99% случаях на нем же и останавливаться.

С хешем, без деревьев.

Здравствуйте, Ватакуси, Вы писали:

В>С хешем, без деревьев.

Если взять из STL вектор, список да хеш, то это дело не очень хитрое, хотя с корректной поддержкой exception-safity, move-semantic и прочим может выйти ой
А вот деревья точно не напишу, про те же красно-черные я помню только то, что они вертятся вроде до 7 раз

В>С хешем, без деревьев.

Какую-то базовую работающую смогу. Если на Python, то даже на листочке без компьютера. Полноценную реализацию, нет, конечно.

На С++ — без вопросов.

Здравствуйте, LaptevVV, Вы писали:

LVV>На С++ — без вопросов.

без деревьев и с функцией отображения слов начинающихся с уже введенных символов

LVV>>На С++ — без вопросов.
S>без деревьев и с функцией отображения слов начинающихся с уже введенных символов
Над функцией — надо помыслить. Потому как там практически всегда используются trie-деревья или всякие подобные варианты
В начальном вопросе не указывалась подобная функция.
Без нее — за 1 день.

Здравствуйте, LaptevVV, Вы писали:

LVV>На С++ — без вопросов.

У тебя работа такая, возможно даже лабу такую принимаешь

LVV>>На С++ — без вопросов.
GIV>У тебя работа такая, возможно даже лабу такую принимаешь
Не, лабы нет.
Но в слайдах я им показываю...

Здравствуйте, CreatorCray, Вы писали:

CC>Здравствуйте, sergey2b, Вы писали:

S>>с функцией отображения слов начинающихся с уже введенных символов
CC>Для такого будет удобнее какой нить вариант radix tree, например patricia trie, но не hash как ты просишь.
Это если доходить до слова посимвольно.
А если слово целиком без поиска посимвольно — то лучше хеша ничего нет.
У меня пацаны пишут транслЯторы с ассемблера — там таблицу имен делают все. Оно — то самое.

Здравствуйте, sergey2b, Вы писали:

S>Здравствуйте, Ватакуси, Вы писали:

В>>С хешем, без деревьев.

S>и поместить весь английский или русский словари в 64к ROM + на манимупляцию с ним еще 64к РАМ

S>задача абсолютно реальная для электроных пишуших машинок
S>я поучаствовал в ее решении в 89 году на z80

а ты часом не путаешь словарь и словарь? вроде слова одинаковые — но есть небольшой ньюанс

Здравствуйте, sergey2b, Вы писали:

S>задача абсолютно реальная для электроных пишуших машинок
S>я поучаствовал в ее решении в 89 году на z80
Реальная. Ключевое слово, по которому гуглить это trie. Плюс там можно очень хорошо все упаковать, если у тебя планируется только поиск делать, а вставка делается один раз при заполнении словаря. Навскидку детали не помню как это делается, но помню где это посмотреть.

Здравствуйте, sergey2b, Вы писали:

В>>С хешем, без деревьев.

S>и поместить весь английский или русский словари в 64к ROM + на манимупляцию с ним еще 64к РАМ
Да, trie прожорливый до памяти.

S>задача абсолютно реальная для электроных пишуших машинок
S>я поучаствовал в ее решении в 89 году на z80

С графом, automata? А зачем ему хеш?

Здравствуйте, Ватакуси, Вы писали:

В>С хешем, без деревьев.

Смогу, и с линейным списком в качестве слотов и с гробовыми камнями (или как там называется, когда он крутится, пока не найдёт место). Деревья не смогу. Красно-чёрные даже не знаю, как работают. АВЛ деревья когда-то давно в универе писал, может если хорошо посижу. то и вспомню, что там куда вертится, но скорей всего не вспомню.

LVV>На С++ — без вопросов.

И разрешение коллизий? По памяти?

В упомянутом питоне это делается как-то так. Не самый простой алгоритм.

Inside the CPython, dictionary is a C structure, PyDictObject:

struct PyDictObject {
    PyObject_HEAD
    Py_ssize_t ma_fill;  /* # Active + # Dummy */
    Py_ssize_t ma_used;  /* # Active */
    Py_ssize_t ma_mask;

    PyDictEntry *ma_table;
    PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
    PyDictEntry ma_smalltable[PyDict_MINSIZE];
};

typedef struct {
    Py_ssize_t me_hash;
    PyObject *me_key;
    PyObject *me_value;
} PyDictEntry;

The fields in the data structure are:

ma_fill

Number of active and dummy entries. If you delete a key, the entry will become
a dummy entry and ma_fill remains the same, if you add a new key and the new
key doesn't occupy a dummy entry, this is increased by 1.

ma_used

Number of active entries. If you add a new key, it is increased by 1, if you
delete a key, it is decreased by 1.

ma_mask

Bitmask of the hash table, the table contains ma_mask + 1 slots. We store the
mask instead of the size because when we are looking up the entry for a key,
`slot = key_hash & mask` is used to get the slot index.

ma_table

An array of `PyDictEntry` structures, the `PyDictEntry` contains the key object,
the value object, and the key's hash, the key's hash is stored as a cache, for
example, when we are searching for a key, we can use the cached hash to perform
a fast comparison.

ma_lookup

A pointer to the function used to look up keys. Initially this is set to
`lookdict_string`, `lookdict_string` assumes that the dictionary keys are all
`PyStringObject`, this is an optimization so that looking up a key can be much
faster for these `StringDictObject`. If a key is not a `PyStringObject`, the
`ma_lookup` is changed to a general lookup function which is slower.

ma_smalltable

An eight slot hash table. Small dictionaries can be stored here and no `malloc()`
would happen.

DUMMY = 'dummy'

def openAddressingProbe(table, key, hash):
    free_slot = None
    perturb = hash
    i = slot_index = hash & ma_mask
    while table[slot_index] is not None and table[slot_index].key != key:
        if table[slot_index].key is DUMMY and free_slot is None:
            free_slot = slot_index
        i = (5 * i + perturb + 1)
        slot_index = i & ma_mask
        perturb >>= 5
    if table[slot_index] is None and free_slot is not None:
        return free_slot
    return slot_index

В>>С хешем, без деревьев.

AG>С хешем не так сложно, я, скорее, с баллансировкой дерева не справлюсь.
Вот на голом С питоновская реализация.

Правда не сложно?
https://github.com/python/cpython/blob/master/Objects/dictobject.c

Здравствуйте, elmal, Вы писали:

E>Здравствуйте, sergey2b, Вы писали:

S>>задача абсолютно реальная для электроных пишуших машинок
S>>я поучаствовал в ее решении в 89 году на z80
E>Реальная. Ключевое слово, по которому гуглить это trie. Плюс там можно очень хорошо все упаковать, если у тебя планируется только поиск делать, а вставка делается один раз при заполнении словаря. Навскидку детали не помню как это делается, но помню где это посмотреть.


нет, средний словарь 10 тыс слов, среднее слово 5 символов, у вас только на поинтеры уйдет 20к и 60к на хранение оригинальных слов, а памяти 64 ну или 128к

надо гуглить n-gram
здесь описанно развитие идеи но можно сделать хитрей, что бы решить проблемму сс словом водка — тынц

Здравствуйте, LaptevVV, Вы писали:

LVV>>>На С++ — без вопросов.
В>>И разрешение коллизий? По памяти?
LVV>Ну, а какие проблемы-то?
LVV>У меня позавчера был экзамен как раз по алгоритмам.
LVV>Дык мне студенты все рассказали: и про хеши, и про коллизии...
LVV>

Проффесор поделитесь пожалуйста вопросами которые вы сейчас даете по алгоритмам и С++

LVV>>Ну, а какие проблемы-то?
LVV>>У меня позавчера был экзамен как раз по алгоритмам.
LVV>>Дык мне студенты все рассказали: и про хеши, и про коллизии...
LVV>>
В>Так это они рассказали. А ты написать сможешь?-)
Ну дык рассказали же!
А память у меня всегда была ХОРОШАЯ...
Но писать сейчас не буду — очень много других дел.

Здравствуйте, Hobbes, Вы писали:

В>>С хешем, без деревьев.

H>Это всё интересно... Но часто ли монтажнику на собеседовании дают задание — собрать перфоратор из уголка, фанеры и проволоки?

А какое отношение монтажник имеет к программисту?

Здравствуйте, vsb, Вы писали:

vsb>А какое отношение монтажник имеет к программисту?

Тот и другой соблюдают процесс и достигают результата.

Здравствуйте, Hobbes, Вы писали:

vsb>>А какое отношение монтажник имеет к программисту?

H>Тот и другой соблюдают процесс и достигают результата.

Очень общее определение. Любовник тоже соблюдает процесс и достигает результата. Программист, кстати, нередко не достигает результата, несмотря на соблюдение процесса, поскольку профессия творческая и не каждая задача каждому по силе.

В>>С хешем, без деревьев.

H>Это всё интересно... Но часто ли монтажнику на собеседовании дают задание — собрать перфоратор из уголка, фанеры и проволоки?
Может, мне везёт, но меня 3 раза просили написать словарь.

Здравствуйте, Ватакуси, Вы писали:

В>>>С хешем, без деревьев.

H>>Это всё интересно... Но часто ли монтажнику на собеседовании дают задание — собрать перфоратор из уголка, фанеры и проволоки?
В>Может, мне везёт, но меня 3 раза просили написать словарь.

Может, ты просто ходишь в такие места?

Здравствуйте, Ватакуси, Вы писали:

В>Может, мне везёт, но меня 3 раза просили написать словарь.

Где собеседуетесь, в России или за бугром? На какую позицию?

Здравствуйте, Ватакуси, Вы писали:

В>С хешем, без деревьев.

с хешем думаю напишу. Там не должно быть сложно. Списки подвешенные к хеш таблице.
единственно что — рехешинг при достижении размера > 75% capacity никогда не решал но думаю тоже не должно быть сложно, но надо подумать как эффективно перетащить на новое место.

дерево кстати тоже делал в 2010 или 2011 году, AVL только, RB не знаю как.
долго тупил при этом но в итоге работало.

В>>Может, мне везёт, но меня 3 раза просили написать словарь.

S>Где собеседуетесь, в России или за бугром? На какую позицию?
Не поверишь, все эти случаи произошли когда на меня выходили какие-то люди и без подготовки просили пройти собеседование в обалденные конторы, про которые они не могут много рассказать, ибо NDA! :D
Время было, я проходил, но толку, понятно, 0. Потом или пропадали или конторы совсем не интересные или денег зажимали.

Здравствуйте, Ватакуси, Вы писали:

В>>>Может, мне везёт, но меня 3 раза просили написать словарь.

S>>Где собеседуетесь, в России или за бугром? На какую позицию?
В>Не поверишь, все эти случаи произошли когда на меня выходили какие-то люди и без подготовки просили пройти собеседование в обалденные конторы, про которые они не могут много рассказать, ибо NDA! :D
В>Время было, я проходил, но толку, понятно, 0. Потом или пропадали или конторы совсем не интересные или денег зажимали.

На вопрос так и не ответили Т.е. это были забугорные конторы? Находили по резюме или рекомендациям? Резюме на SO было?

Здравствуйте, CreatorCray, Вы писали:

S>>с функцией отображения слов начинающихся с уже введенных символов
CC>Для такого будет удобнее какой нить вариант radix tree, например patricia trie, но не hash как ты просишь.

Merkle Tree- с хешом. Правда я хз, как оно поможет с "начинающихся с уже введённых символов".

Здравствуйте, Ватакуси, Вы писали:

В>Не поверишь, все эти случаи произошли когда на меня выходили какие-то люди и без подготовки просили пройти собеседование в обалденные конторы, про которые они не могут много рассказать, ибо NDA! :D

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

Здравствуйте, $$, Вы писали:

$>Merkle Tree- с хешом.
Шта?

$> Правда я хз, как оно поможет с "начинающихся с уже введённых символов".
Да примерно как собаке — пятая нога.

Здравствуйте, $$, Вы писали:

$>Здравствуйте, CreatorCray, Вы писали:

S>>>с функцией отображения слов начинающихся с уже введенных символов
CC>>Для такого будет удобнее какой нить вариант radix tree, например patricia trie, но не hash как ты просишь.

$>Merkle Tree- с хешом. Правда я хз, как оно поможет с "начинающихся с уже введённых символов".

Сильно, однако. А давайте сделаем так. ХЗ, как оно поможет решению задачи, но давайте сделаем. Как это понимать

Здравствуйте, Ватакуси, Вы писали:

В>С хешем, без деревьев.

с хреновой хеш функцией(с большой вероятностью коллизий) — да

TMU>>А как же ты работаешь??
KP>Зажмуриваюсь и по клавиатуре херачу, как же еще?
KP>А ты сбалансированные деревья по памяти пишешь? Уважаю!



Да ладно, я примерно также, на ощупь...

В>С хешем, без деревьев.

на ассемблере ЕС ЭВМ на векторах

Здравствуйте, Ватакуси, Вы писали:

В>С хешем, без деревьев.
А смысл в нём без подготовки? Хороший словарь — это который проходил "подготовку" лет 20 (отлаживался и тэстировался на реальных задачах).

Здравствуйте, Андруха, Вы писали:

В>>С хешем, без деревьев.

А>с хешем думаю напишу. Там не должно быть сложно. Списки подвешенные к хеш таблице.
А>единственно что — рехешинг при достижении размера > 75% capacity никогда не решал но думаю тоже не должно быть сложно, но надо подумать как эффективно перетащить на новое место.

А в чём проблема? Тупо создаёшь новый массив, в цикле у старого delete у нового insert и всё.

Здравствуйте, LaptevVV, Вы писали:

LVV>А если слово целиком без поиска посимвольно — то лучше хеша ничего нет.
А что тут означает слово "лучше"? Лучше по какому критерию?

LVV>У меня пацаны пишут транслЯторы с ассемблера — там таблицу имен делают все. Оно — то самое.
А они на чём пишут, что им нужно реализовывать словарь с нуля? На чистом Си?

LVV>>А если слово целиком без поиска посимвольно — то лучше хеша ничего нет.
E>А что тут означает слово "лучше"? Лучше по какому критерию?
Хеш = О(1)
LVV>>У меня пацаны пишут транслЯторы с ассемблера — там таблицу имен делают все. Оно — то самое.
E>А они на чём пишут, что им нужно реализовывать словарь с нуля? На чистом Си?
Им с нуля как раз не нужно. Они STL используют — map и/или unodered_map/

Здравствуйте, Sinclair, Вы писали:

S>Вот топ-10 вопросов, которые профессора сейчас дают по алгоритмам и C++
S>1. Мой экран всем видно?
S>...
Нулевой:
0. Меня слышно? Меня всем слышно?

Здравствуйте, LaptevVV, Вы писали:

LVV>>>А если слово целиком без поиска посимвольно — то лучше хеша ничего нет.
E>>А что тут означает слово "лучше"? Лучше по какому критерию?
LVV>Хеш = О(1)
1. Видимо речь идёт о времени исполнения каких-то операций? Каких?
2. Очевидно, что, как минимум О(длина_строки). По идее, если не нужно экономить память, то бор имеет такую же асимптотику при добавлении/поиске...

E>>А они на чём пишут, что им нужно реализовывать словарь с нуля? На чистом Си?
LVV>Им с нуля как раз не нужно. Они STL используют — map и/или unodered_map/
Ну в STL больше ничего подходящего нет, вроде как..

PM>Хорошо, что вы рассказываете студентам про O(1), но стоит сказать и про разные константы такой сложности. И вообще, как всё в современных системах сложно
Это все понятно. Я им рассказываю даже случаи из моей практики.
Здесь несколько лет задавал вопрос, но повторю.
Писал на стандартном С++ прогу научную по перколяции.
Надо было написать обход графа — специального.
В качестве контейнера поставил дек — удобнее так было.
Написал в студии — все работает.
Перенес в Code::Blocks — тоже работает.
А поскольку прога — очень критична по времени, надо заказчику показывать в каком-нить виде время выполнения.
Стандартно поставил clock() спереди-сзади, вывожу в секундах с 3 знаками.
И замечаю, что прога из Code::Blocks примерно в 5 раз быстрее работает.
Предыдущие проги отличались по времени примерно процентов на 10.
А тут в 5 раз!
В результате выискивания блох под ковром — ничего не нашел.
Задал вопрос на РСДН.
Дня через 2 один пацан пишет — проблема в реализации дека в Студии.
Хреново реализована работа с памятью.
Порекомендовали переделать под вектор (о чем я уже и сам подумывал).
Естественно, после рефакторинга под вектор все встало на свои места: разница во времени примерно 10-12% в пользу gcc.
Так что мы не голой теорией занимаемся.

LVV>>>>А если слово целиком без поиска посимвольно — то лучше хеша ничего нет.
E>>>А что тут означает слово "лучше"? Лучше по какому критерию?
LVV>>Хеш = О(1)
E>1. Видимо речь идёт о времени исполнения каких-то операций? Каких?
E>2. Очевидно, что, как минимум О(длина_строки). По идее, если не нужно экономить память, то бор имеет такую же асимптотику при добавлении/поиске...
Ты как с Луны вообще.
Операции поиска и вставки в словарь.
Хеш-функция — это вычисление значения многочлена от строки, так что никаких О(длина строки тут нет).
Но коэффициент некий есть, да.
E>>>А они на чём пишут, что им нужно реализовывать словарь с нуля? На чистом Си?
LVV>>Им с нуля как раз не нужно. Они STL используют — map и/или unodered_map/
E>Ну в STL больше ничего подходящего нет, вроде как.
Можно еще самому написать... Они у меня лабы пишут по алгоритмам — на основе самостоятельно реализованного класса.
И сравнивают время работы стандартных и своих.
Очень полезные упражнения.

Здравствуйте, LaptevVV, Вы писали:

LVV>>>Хеш = О(1)
E>>1. Видимо речь идёт о времени исполнения каких-то операций? Каких?
E>>2. Очевидно, что, как минимум О(длина_строки). По идее, если не нужно экономить память, то бор имеет такую же асимптотику при добавлении/поиске...
LVV>Ты как с Луны вообще.
LVV>Операции поиска и вставки в словарь.
Как минимум ещё возможна операция удаления...

LVV>Хеш-функция — это вычисление значения многочлена от строки, так что никаких О(длина строки тут нет).
Это как так? Ты хочешь сказать, что от строки в 10 букв и в 10 мегабайт хэш за одинаковое время считается?
Кроме того, ещё в хэш-таблице, в конце, надо сравнивать строку со строкой, при наличии коллизий, неоднократно. Это тоже пропорционально длине строки. Так что хэш-таблица строк, по добавлению это никак не меньше O(размер добавляемого текста)? а по поиску никак не меньше O(объём текста, который ищем).
Очевидно бор в этом смысле не хуже, а если не жаль памяти, то и лучше


E>>Ну в STL больше ничего подходящего нет, вроде как.
LVV>Можно еще самому написать... Они у меня лабы пишут по алгоритмам — на основе самостоятельно реализованного класса.
LVV>И сравнивают время работы стандартных и своих.
LVV>Очень полезные упражнения.

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

Здравствуйте, Ватакуси, Вы писали:

В>С хешем, без деревьев.

Давай лучше "malloc" писать

Вот хороший пример.
— Оптимальная реализация.
— Отлажен.
— Хорошо умеет в многоядерность.
— Чистый С, без питоновской мути.
— Много комментариев.
— Всё просто и понятно.
— Ещё и куча отладочных инструментов встроена.

Здравствуйте, LaptevVV, Вы писали:

LVV>Ты в словаре слова видел? Они по 10 метров?
Какая разница? 1 слово в 10 метров или миллион слов по 10 букв -- суммарный объём добавленного в словарь текста будет одинаковый и именно ему будет пропорционально время работы...
Та же асимптотика и для объём текста, который ищем.

LVV>Коллизии разными способами решаются, не только последовательным рехешированием.
Есть способ хеширования, при котором в конце не надо сравнивать со всеми элементами в корзине?

E>>Очевидно бор в этом смысле не хуже, а если не жаль памяти, то и лучше
LVV>Может быть.
такая модальность ответа от преподавателя с твоим стажем доставляет. Неужели студни ни разу такого рода вопросов не задавали?

E>>Ну это да, но если самому писать конкуренты STL-контейнерам, трудно адекватные контексты использования перебрать.
E>>С другой стороны в конкретном случае словаря из строк в что угодно, логичнее написать самом бор и сравнить с STL-ной мапой и хэш-мапой (которая беспорядочная)
LVV>Ну, время будет — попробую.
Пиши, что выйдет!

E>>Очевидно бор в этом смысле не хуже, а если не жаль памяти, то и лучше
Если не жаль памяти, то можно сделать таблицу вообще практически без коллизий, просто увеличив ее размер.
И подобрав хорошую функцию хеширования.

LVV>>Ты в словаре слова видел? Они по 10 метров?
E>Какая разница? 1 слово в 10 метров или миллион слов по 10 букв -- суммарный объём добавленного в словарь текста будет одинаковый и именно ему будет пропорционально время работы...
E>Та же асимптотика и для объём текста, который ищем.
Не. Если я знаю, что у меня "слова" могут быть по 10 метров — я сильно подумаю, как это скажется на реализации.
И, возможно, выберу другой метод.
LVV>>Коллизии разными способами решаются, не только последовательным рехешированием.
E>Есть способ хеширования, при котором в конце не надо сравнивать со всеми элементами в корзине?
Корзина — относительно небольшая по сравнению с таблицей.
Тем более, как я уже в отдельном посте написал, если памяти не жалко, то можно таблицу сделать большой и, тем самым, практически без коллизий.
И функцию хещирования подобрать равномерно распределяющую.
E>>>Очевидно бор в этом смысле не хуже, а если не жаль памяти, то и лучше
LVV>>Может быть.
E> такая модальность ответа от преподавателя с твоим стажем доставляет. Неужели студни ни разу такого рода вопросов не задавали?
Студни про бор не знают...
Они Кнута не читали, а лекций у меня (благодаря минобру и нашему руководству) осталось так мало, что успеть бы про б-деревья рассказать...
E>>>Ну это да, но если самому писать конкуренты STL-контейнерам, трудно адекватные контексты использования перебрать.
E>>>С другой стороны в конкретном случае словаря из строк в что угодно, логичнее написать самом бор и сравнить с STL-ной мапой и хэш-мапой (которая беспорядочная)
LVV>>Ну, время будет — попробую.
E>Пиши, что выйдет!
Обязательно.

Здравствуйте, IID, Вы писали:

нормальный такой malloc на 6000 строк

Здравствуйте, sergey2b, Вы писали:

S>Здравствуйте, IID, Вы писали:

S>нормальный такой malloc на 6000 строк

А сколько надо? Сколько в канонической реализации в CRT?

Здравствуйте, Sharov, Вы писали:

S>А сколько надо? Сколько в канонической реализации в CRT?
В CRT? Как правило нынче ровно одна — вызов системного аллокатора.

Здравствуйте, CreatorCray, Вы писали:

S>>А сколько надо? Сколько в канонической реализации в CRT?
CC>В CRT? Как правило нынче ровно одна — вызов системного аллокатора.

А он как реализован, сколько строк, где посмотреть? Насколько понимаю, можно свой аллокатор подсунуть, верно?

Здравствуйте, Sharov, Вы писали:

S>А он как реализован, сколько строк, где посмотреть?
Зависит от системы жеж.

S>Насколько понимаю, можно свой аллокатор подсунуть, верно?
В смысле перекрыть то, что в CRT?
Да, можно.

Здравствуйте, Ватакуси, Вы писали:

В>С хешем, без деревьев.

Я да, но понимаешь в чём дело: у меня работа такая, трансляторы пишу.