История изменений

Или превращать короткие строки в числа? А смысл? Это будет та же самая хештабля.

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

Это будет та же самая хештабля.

…для которой не нужны будут «ксоры» и в целом какой-либо расчет хеша. Вы просто берете (unsigned int*)(&c), откусывая по sizeof (unsigned int) от строки и пользуетесь этим. Можете, кстати, и префикс кусками нарезать, а не побайтово.

только не откидывая префиксы

Вот именно.

Для начала, благодаря исходному разбиению по длинам ключей, у вас будет O(1) доступ к контейнеру, содержащему искомый ключ, что уже сужает круг поиска в 39 (на самом деле нет, при равномерном распределении длинных ключей больше, чем коротких) раз. За счет этого каждый отдельно взятый контейнер будет содержать значительно меньше элементов, чем если бы все ключи лежали в одном контейнере, и все эти элементы будут одной длины. В данный момент на каждый лист дерева вы затрачиваете 256 * 8 байт лишней памяти. Если вы будете точно знать, что данная нода – лист, вы сможете обойтись без этих затрат. Если вы будете знать обратное, вы сможете обойтись без хранения *value в ноде. Уже этим мое решение улучшает ваш результат.

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

На выходных набросаю код, если вам интересно.

Или превращать короткие строки в числа? А смысл? Это будет та же самая хештабля.

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

Это будет та же самая хештабля.

…для которой не нужны будут «ксоры» и в целом какой-либо расчет хеша. Вы просто берете (unsigned int*)(&c), откусывая по sizeof (unsigned int) от строки и пользуетесь этим. Можете, кстати, и префикс кусками нарезать, а не побайтово.

только не откидывая префиксы

Вот именно.

Для начала, благодаря исходному разбиению по длинам ключей, у вас будет O(1) доступ к контейнеру, содержащему искомый ключ, что уже сужает круг поиска в 39 (на самом деле нет, при равномерном распределении длинных ключей больше, чем коротких) раз. За счет этого каждый отдельно взятый контейнер будет содержать значительно меньше элементов, чем если бы все ключи лежали в одном контейнере, и все эти элементы будут одной длины. В данный момент на каждый лист дерева вы тратите 256 * 8 байт памяти. Если вы будете точно знать, что данная нода – лист, вы сможете обойтись без этих затрат. Если вы будете знать обратное, вы сможете обойтись без хранения *value в ноде. Уже этим мое решение улучшает ваш результат.

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

На выходных набросаю код, если вам интересно.

Или превращать короткие строки в числа? А смысл? Это будет та же самая хештабля.

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

Это будет та же самая хештабля.

…для которой не нужны будут «ксоры» и в целом какой-либо расчет хеша. Вы просто берете (unsigned int*)(&c), откусывая по sizeof (unsigned int) от строки и пользуетесь этим. Можете, кстати, и префикс кусками нарезать, а не побайтово.

только не откидывая префиксы

Вот именно.

Для начала, благодаря исходному разбиению по длинам ключей, у вас будет O(1) доступ к контейнеру, содержащему искомый ключ. За счет этого каждый отдельно взятый контейнер будет содержать значительно меньше элементов, все эти элементы будут одной длины. В данный момент на каждый лист дерева вы тратите 256 * 8 байт памяти. Если вы будете точно знать, что данная нода – лист, вы сможете обойтись без этих затрат. Если вы будете знать обратное, вы сможете обойтись без хранения *value в ноде. Уже этим мое решение улучшает ваш результат.

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

На выходных набросаю код, если вам интересно.

Или превращать короткие строки в числа? А смысл? Это будет та же самая хештабля.

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

Это будет та же самая хештабля.

…для которой не нужны будут «ксоры» и в целом какой-либо расчет хеша. Вы просто берете (unsigned int*)(&c), откусывая по sizeof (unsigned int) от строки и пользуетесь этим. Можете, кстати, и префикс кусками нарезать, а не побайтово.

только не откидывая префиксы

Вот именно.

Для начала, у вас будет O(1) доступ к контейнеру, содержащему этот ключ. За счет этого каждый отдельно взятый контейнер будет содержать значительно меньше элементов, все эти элементы будут одной длины. В данный момент на каждый лист дерева вы тратите 256 * 8 байт памяти. Если вы будете точно знать, что данная нода – лист, вы сможете обойтись без этих затрат. Если вы будете знать обратное, вы сможете обойтись без хранения *value в ноде. Уже этим мое решение улучшает ваш результат.

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

На выходных набросаю код, если вам интересно.

Или превращать короткие строки в числа? А смысл? Это будет та же самая хештабля.

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

Это будет та же самая хештабля.

…для которой не нужны будут «ксоры» и в целом какой-либо расчет хеша. Вы просто берете (unsigned int*)(&c), откусывая по sizeof (unsigned int) от строки и пользуетесь этим. Можете, кстати, и префикс кусками нарезать, а не побайтово.

только не откидывая префиксы

Вот именно.

Для начала, у вас будет O(1) доступ к контейнеру, содержащему этот ключ. За счет этого каждый отдельно взятый контейнер будет содержать значительно меньше элементов, все эти элементы будут одной длины. Урезание префиксов позволит вам хранить не массивы строк, а массивы интов, опять же, достаточно короткие. Размер массивов не фиксированный, но небольшой, реаллокация будет быстрой. Это хотя и может оказаться несколько медленнее полного дерева, но сэкономит вам достаточно памяти. В данный момент на каждый лист дерева вы тратите 256 * 8 байт памяти. Если вы будете точно знать, что данная нода – лист, вы сможете обойтись без этих затрат. Если вы будете знать обратное, вы сможете обойтись без хранения *value в ноде. Уже этим мое решение улучшает ваш результат.

На выходных набросаю код, если вам интересно.

Или превращать короткие строки в числа? А смысл? Это будет та же самая хештабля.

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

Это будет та же самая хештабля.

…для которой не нужны будут «ксоры» и в целом какой-либо расчет хеша. Вы просто берете (unsigned int*)(&c), откусывая по sizeof (unsigned int) от строки и пользуетесь этим. Можете, кстати, и префикс кусками нарезать, а не побайтово.

только не откидывая префиксы

Вот именно.

Для начала, у вас будет O(1) доступ к контейнеру, содержащему этот ключ. За счет этого каждый отдельно взятый контейнер будет содержать значительно меньше элементов, все эти элементы будут одной длины. Урезание префиксов позволит вам хранить не массивы строк, а массивы интов, опять же, достаточно короткие. Размер массивов не фиксированный, но небольшой, реаллокация будет быстрой. Это хотя и может оказаться несколько медленнее полного дерева, но сэкономит вам достаточно памяти. В данный момент на каждый лист дерева вы тратите 256 * 8 байт памяти. Если вы будете точно знать, что данная нода – лист, вы сможете обойтись без этих затрат. Если вы будете знать обратное, вы сможете обойтись без хранения *value в ноде. Уже этим мое решение улучшает ваш результат.