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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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