Самый быстрый Индиан

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

Легендарный супероптимизированый алгоритм, который реализует весьма сложные Trie структуры данных и топчет вот эти вот эти ваши самые реализации ассоциативных массивов std::map, glib, dictionary.net и прочью заморскую попсу в разы, а то и на порядок.

github.com/Bazist/HArray (Windows & Linux)

PS: Готовлю потихоньку раскат гром и молнии на хабр, но пока потренируемся на Доу.

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті

👍ПодобаєтьсяСподобалось1
До обраногоВ обраному3
LinkedIn

Найкращі коментарі пропустити

1. Не надо «the most optimized». Просто «Trie implementation in C++», или «Fast Trie implementation». Но лучше без «fast», если нет тестов и легко воспроизводимых benchmark’ов.
2. Tab for indentation, spaces for alignment. Можно забить, и получить срач на тему spaces-vs-tabs вместо обсуждения кода когда оно пойдёт на Reddit.
github.com/...ValuesByRange.cpp#L22-L29
3. Не надо оставлять закомментированные блоки. Если один лишний повод для срача.
github.com/...dKeyAndValue.cpp#L22-L204
4. StdAfx.h, windows.h, int _tmain(int, _TCHAR*[]) — wtf? system("pause")?!
5. printf’ы в C++ коде? После include <iostream>? Ещё один повод для срача.

6*. Не эксперт в VS, но я бы ожидал там два проекта: собственно библиотеку, и отдельно от неё демку/тест/пример который main.c.
7*. Зачем в .gitattributes строки с 3-й до конца? Зачем мусор в .gitignore? VS реально столько оставляет в проекте, или это просто копипаст откуда-то?

8. Обычные Makefile-ы сильно увеличат шансы сборки левыми людьми.
Соответственно шансы получить отзывы по сути, а не по форматированию.
Или CMakeLists, и поубирать VS проекты.

9. Тесты, или что-то хотя бы отдалённо похожее на тесты. Сильно рекомендуется. Очень сильно.

Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Решил установить harray. Вот что делал согласно readme.mod for Win10

C:\Users\1>cmake --version
cmake version 3.21.1
CMake suite maintained and supported by Kitware (kitware.com/cmake).
C:\Users\1\home\c++>cd harray
C:\Users\1\home\c++\harray>mkdir build
C:\Users\1\home\c++\harray>cmake -Bbuild
-- Building for: NMake Makefiles
CMake Error at CMakeLists.txt:3 (project):
  Running
   'nmake' '-?'
  failed with:
   Не удается найти указанный файл
CMake Error: CMAKE_CXX_COMPILER not set, after EnableLanguage
-- Configuring incomplete, errors occurred!
See also "C:/Users/1/home/c++/harray/build/CMakeFiles/CMakeOutput.log".
C:\Users\1\home\c++\harray>

Как это исправить?

Здесь пишут решение
stackoverflow.com/...​compiler-and-cxx-compiler

Но под Windows все проще. Если у тебя установлена студия то просто клонируешь репозиторий и открываешь готовый солюшин

github.com/...​r/HArray_VisualStudio.sln

Я сделал так только что: скачал с гитхаба и создал папку harray и содержимое zip забросил внутрь, затем «открыть с помощью vscode» на sln файле.
Что делать дальше?

Попробовать сбилдить + запустить

А что писать в байлд таске? (tasks.json)

{
    // See https://go.microsoft.com/fwlink/?LinkId=733558
    // for the documentation about the tasks.json format
    "version": "2.0.0",
    "tasks": [
        {
            "label": "build",
            "type": "shell",
            "command": "msbuild",
            "args": [
                // Ask msbuild to generate full paths for file names.
                "/property:GenerateFullPaths=true",
                "/t:build",
                // Do not generate summary otherwise it leads to duplicate errors in Problems panel
                "/consoleloggerparameters:NoSummary"
            ],
            "group": "build",
            "presentation": {
                // Reveal the output only if unrecognized errors occur.
                "reveal": "silent"
            },
            // Use the standard MS compiler pattern to detect errors, warnings and infos
            "problemMatcher": "$msCompile"
        }
    ]
}

Хм, первый раз сталкиваюсь.
У себя ставил обычную бесплатную VS Community
visualstudio.microsoft.com/ru/vs/community

Может завтра будет время поставлю VS Code посмотрю подробнее как под ней запустить.

Кул. А видео процесса можешь записать? VSDC пишет неплохо. Я им пользуюсь.
У тебя ведь *nix? Вдруг не подойдет винде? В общем, пойду я тоже гуглить ошибку.
Посмотрим чего найду.

У тебе не налаштований PATH до компілятора. Спробуй те саме запустити у VS Developer Console чи як там у тебе воно називається (шукай в Start->Visual Studio...). Або на сайті МС де качав dev tools читай як налаштовувати.

У меня есть mingw, он может компилировать.
Осталось написать bat чтобы:

cmake_minimum_required(VERSION 3.10)
project(HArray LANGUAGES CXX)
# set(CMAKE_CXX_STANDARD 11)
add_library(harray STATIC
  src/HArray_delValueByKey.cpp
  src/HArray_getKeysAndValuesByRange.cpp
  src/HArray_getValueByKey.cpp
  src/HArray_hasPartKey.cpp
  src/HArray_insert.cpp
  src/HArray_insertOrGet.cpp
  src/HArray_rebuild.cpp
  src/HArray_scanKeysAndValues.cpp
  src/HArray_shrink.cpp
  src/HArray_test.cpp
  src/HArrayGeneric.cpp)
target_include_directories(harray PUBLIC ${CMAKE_CURRENT_SOURCE_DIR}/harray)
add_executable(HArrayBenchmark benchmark/HArrayBenchmark.cpp)
target_link_libraries(HArrayBenchmark harray)

Чтобы тот учитывал все вышеприведенное.
А все эти более сложные штуки cmake, nmake соответственно накапливают все больше и больше несоответствий версий и других нестыковок.
Когда я встречаю такое, я чаще всего ищу более абстрактное решение и пытаюсь запустить его.

Ніякі bat-файли не потрібні, cmake для того і придумали, щоб не писати для кожної платформи на компілятору скріпти.

Твій mingw скоріше за все не прописаний у PATH і cmake через те його не бачить і намагається використовувати майкрософтовські тулзи — звідти і виклик nmake.

Почитай документацію і налаштуй свій mingw для початку — sourceforge.net/...​GeneralUsageInstructions

Вот наше решение:

C:\Users\1\home\c++\harray>cmake -Bbuild2 -G "MinGW Makefiles"
-- The CXX compiler identification is GNU 10.3.0
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Check for working CXX compiler: C:/msys64/mingw64/bin/g++.exe - skipped
-- Detecting CXX compile features
-- Detecting CXX compile features - done
-- Configuring done
-- Generating done
-- Build files have been written to: C:/Users/1/home/c++/harray/build2
C:\Users\1\home\c++\harray>

Кто-то как залезет в код, как вытянет алгоритм, как запатентует его...

5 лет уж прошло, а Германа все нет ...
На самом деле, самая большая ценность начинается,
когда делается грамотный тюнинг уже под конкретную задачу.
Как начал в свое время выступление Matt Kulukundis, мы думали что key/value это простая задача, но мы провалились в кротовую нору с 100500 ньюансов.
На самом деле это как устройство клетки в организме, все основные фокусы начинаются на уровне микромира. А владелецей этой клетки, ну может быть какая-то муха, комар или грибок. Вообщем ничего интересного.

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

int main()
{
  HArray ha;
  ha.init();
    
  uint32 key1[] = { 10 };  
  ha.insert(key1, sizeof(key1), 23);
  
  uint32 value;
  uint32 dummy_var[] = { 10 }; 
  if(ha.getValueByKey(key1, sizeof(key1), value))
  {
     printf("value: %d \n", value);
  } else {
     printf("NO KEY \n");
  }

  return 0;
}
компілював під Xubuntu 18, «g++ testharray.cpp -o testharray libharray.a && ./testharray
». на виході постійно NO KEY.

Вот здесь нужно подправить.
Нативно длина ключа в сегментах.
Один сегмент = 4 байта.

ha.insert(key1, sizeof(key1)/4, 23);

дякую, поправив. але результат був такий самий, то я ще в getValue поділив, тоді наче спрацювало.

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

HArrayChar ha;
	ha.insert("dou", 3, "hello", 5);
	
	char sayHello[16];
	uint32_t valueLen;

	if (ha.getValueByKey("dou", 3, sayHello, valueLen))
	{
		printf("Key with value %s is found.", sayHello);
	}
	else
	{
		printf("Key is not found.");
	}

	return 0;

скажіть, в чому може бути причина ще такої проблеми: коли я запускаю код

int main()
{
  HArray ha;
  ha.init(10);
  
  uint32 value;
  
  uint32 key1[] = { 10 };
  uint32 key2[] = { 20 };
  
  ha.insert(key1, sizeof(key1)/4, 1);
  //ha.insert(key2, sizeof(key2)/4, 2);
  
  if(ha.getValueByKey(key1, sizeof(key1)/4, value))
  {
     printf("{ 10 } value: %d \n", value);
  } else {
     printf("{ 10 } NO KEY \n");
  }

  return 0;
}
все відпрацьовує добре «{ 10 } value: 1», але варто мені розкоментувати закоментований рядок і видає «{ 10 } NO KEY »?

Хм, вотето поворот. Пофиксил, в мастере есть изменения.
PS: Предистория. Там интерфейс немного менялся недавно

getValueByKey

возвращает true/false. А раньше возвращала сразу value. И не было понятно если вернула 0, это нет ключа или это велью 0. При изменении этого интерфейса был баг, в одном месте забыл проставить return true явно, если значение найдено.

Мені здається тут баг — github.com/...​r/src/HArrayGeneric.h#L64. Має бути не += 2, а *= 2.

Мені здається тут баг — github.com/...​r/src/HArrayGeneric.h#L64. Має бути не += 2, а *= 2.
Точно, пофиксил. Спасибо.

Сорри, не увидел что уже пулл реквест на эти изменения создан.
Замержил.

Как же так, ведь ты зуб давал что багов нет, и после миллиона операций вставки и чтения багов быть не может? ;)

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

Це ІМО класичний приклад коли «непотрібні» юніт-тести зловили б таку елементарну опечатку миттєво. От прямо можна студентам показувати для демонстрації того, що код без юніт-тестів не може вважатися якісним аж ніяк.

Ну что господа, похоже нет выбора.
Будем пилить паттерн матчинг для ключей. Нужно искать ключи не только по префиксам но и по окончанию ключа без фулскана. Это понадобится через недели две.
img2.joyreactor.cc/...​удент-машина-2410784.jpeg

Будем пилить паттерн матчинг для ключей

Реализовал поиск ключей в контейнере по постфиксу (не префиксу) за время лучше О(N).
Оказалось, это было не сложно, но сделано через малоочевидный костыль в юае, сейчас думаю как обернуть в нормальный юай.

Конечно это крутая функциональность, которая открывает дверь в мир версионных кей велью стореджей. Тоесть в мир офлайновых систем которые умеют мержится, распределенных транзакций и много чего еще. Ведь если добавить в конец ключа его версию, то можно быстро находить ключи нужной версии в контейнере, делать срез (снапшот) кей велью контейнера на определенный момент времени (Way Back Machine). Причем в HArray оверхед для отслеживания историчности изменений достаточно небольшой. И вот теперь можно быстро получать срез состояния контейнера на какойто момент времени, благодаря скану ключей по постфиксным сегментам.

PS В честь этого события предлагаю прослушать композицию Hans Zimmer — Time.
youtu.be/RxabLA7UQ9k
Друзья, мы стали ещё чуть ближе к совершенным системам.

Запили биткоин-про и сруби бабла.
P.S. Музычка приятная.

Дауж, харрей не перестает удивлять. Оказывается сканировать ключи в контейнере можно не только по префиксам или по диапазону ключей от и до, как в обычном трай, но и по шаблону. Например найти все ключи которые заканчиваются на XXX за время существенно быстрее O(N) хоть и не O(1) или O(x) где х размер диапазона.
Это вынос мозга, но это факт. Такой скан за время быстрее О(N) абсолютно невозможен не в хештаблицах, не в сортированных бинарных деревьях. А здесь может быть. Это было неочевидно.

Что такое «существенно быстрее О(n)»? Точная оценка есть?

Зависит от природы ключей.
Бест кейс будет примерно таким. Если К это длина ключа, константа, то
О(K) + (O(1) или O(M)), где М всегда не более 8 при любом количестве ключей. Что по нотации большого О всеравно считается О(1).

Такой кейс возможен для пальмовых деревьев. Что такое пальма ? Это дерево которое слабо ветвится в своих корнях, но сильно ветвится в своей короне.

Ворст кейс, будет приближатся к О(N) но всегда будет его чуть-чуть меньше. Ворст кейс можно добится когда у нас дерево типа бамбук. Тоесть ключей много и они все имеют свой индивидуальный корень.

Если написал слишком сумбурно, есть простой пример. Допустим нам нужно искать людей по Имя/Фамилия.
Мы можем сформировать все ключи как [Имя][Фамилия] и получим пальму. Имен мало уникальных, фамилий много уникальных. Поэтому это дерево будет мало ветвится в своем корне и сильно ветвится в своей короне.
В другом варианте, мы можем сформировать все ключи как [Фамилия][Имя]. Тогда получим бамбук. Уникальных фамилий много и дерево в самом начале будет сильно ветвится и делится на индивидуальные иерархии.

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

Самое забавное, что пальма в природе встречается значительно чаще чем бамбук. Любое дерево по своей природе ближе к пальме чем к бамбуку. Весь ряд натуральных чисел классическая пальма. Если мы запихнем весь ряд чисел в виде ключей в харрей то обнаружим что старшие разряды чисел ветвятся намного меньше чем младшие, образовуя пальмовидное дерево. Настоящий кондовый бамбук можно получить только с идеальным генератором случайных чисел. Но и этот бамбук при количестве рандом ключей стремящемся к бесконечности будет вырождаться постепенно в пальму.

Ворст кейс, будет приближатся к О(N) но всегда будет его чуть-чуть меньше

0.5* O(n) = 5*O(n) = O(n)

0.5* O(n) = 5*O(n) = O(n)

Есть комплексити и О(n*n) и О(n/2).
Если тебе в худшем случае нужно меньше/больше обойти чем N, то значение в скобках может изменятся как в большую так и в меньшую сторону.
www.quora.com/...​2-a-valid-time-complexity

В том и дело что O(чуть меньше n) не бывает. Если это O(n/2) так и пиши. 0.5 * O(n) != O(n/2)

Мое упущение, буду расти :)))

Дуже неочевидний сарказм в пості ІМО, легко сприйняти за серйозний текст.

Профессор по ссылке пишет что формально можно и так.
www.quora.com/...​2-a-valid-time-complexity

В последнем тестовом примере, при поиске ключей по постфиксным сегментам, обошел 8 ключей вместо 2048, которые находились в контейнере. Называть такой скан O(N), сорян, слишком грубо. О(1) назвать тоже не могу, потому что гдето это будет 8 ключей, где-то 20, где-то 100. Но всегда существенно меньше N.

Профессор по ссылке пишет что формально можно и так.

Исходя из того что есть врачи антивакцинаторы, можно одним движением руки вывести утверждение, что есть профессора, для которых O(n) != O(n/8) :-)

В последнем тестовом примере, при поиске ключей по постфиксным сегментам, обошел 8 ключей вместо 2048, которые находились в контейнере. Называть такой скан O(N), сорян, слишком грубо. О(1) назвать тоже не могу, потому что гдето это будет 8 ключей, где-то 20, где-то 100. Но всегда существенно меньше N.

Большое О показывает как быстро растёт количество операций на поиск относительно количества ключей n. Если на 2048 ключей было 100 операций, а на 20480 — 1000, то это все то же O(n). Тебе нужно позапускать контейнер итеративно и посмотреть для разных n, какие будут верхние значения (это O), минимальные и средние (amortized). И вывести это на график.

Большое О показывает как быстро растёт количество операций на поиск относительно количества ключей n. Если на 2048 ключей было 100 операций, а на 20480 — 1000, то это все то же O(n). Тебе нужно позапускать контейнер итеративно и посмотреть для разных n, какие будут верхние значения (это O), минимальные и средние (amortized). И вывести это на график.

Знаете чем специалист отличается от не специалиста. Не специалист видит только белое и черное. А специалист видит еще 100500 оттенков между этими двумя цветами. В данном случае невозможно вывести эту оценку универсально и точно, поскольку она очень сильно зависит не от количества ключей, а от топологии самих ключей формирующих само дерево. Поэтому оценка будет гулять от О(1) best case до О(N) worst case. Примерно как в хештаблицах в зависимости от природы, количества ключей и качества хешфункции.

О(N) worst case

Ты сам себе и ответил.
Твой алгоритм O(n).

Вот сравни свои выкладки с сортировкой:

Пузырёк это O(n*n), но всем понятно что полностью развернутый массив встречается крайне редко и в подавляющем большинстве случаев пузырёк закончит свою работу быстрее. Но от этого его оценка не будет гулять от O(1) до O(n*n). Она так и останется O(n)

А вот не все так однозначно. Тогда бы для _классической_ хештаблицы писали бы оценку О(N) а не О(1). Ведь если сойдутся на небе звезды и все хеши будут бить в одну ячейку, то хештаблице придется сканировать весь сет ключей. Она будет мало чем отличатся от обычного связного списка.
Но вероятность этого настолько мала, что этим можно пренебречь и поставить О(1).

Но вероятность этого настолько мала, что этим можно пренебречь и поставить О(1).

Это big theta, а не O

Для твоего алгоритма и реализации:
Big O = N
Big Theta = 1 (скорее всего 1, если сразу нашла ключ)
Big Omega = где то посредине

представь, что тебя будут дудосить — как в таком случае справится хеш таблица с рандомизированной хеш функцией, и как справится твоя структурка?

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

Ні, почитай що таке big O.

А вот не все так однозначно. Тогда бы для _классической_ хештаблицы писали бы оценку О(N) а не О(1).

А никто вменяемый O(1) и не пишет. Пишут про _амортизированное_ O(1) с возможностью получать O(N) в особых случаях. В частности, если по новому ключу производится полное переформатирование таблицы под новый размер, то именно эта вставка будет O(N).

В Java начиная с 8 сделано, что если длина списка в корзине превышает некоторую границу (около 10), вместо него втыкается RBT-based мапа (конкретно в этой корзине).
Таким образом они сокращают эту часть до O(log N). Средний случай всё равно остаётся O(1).

Останнє речення говорить про те, що так писати можна, але це безграмотно:
In practice, however, writing O(n/2) is bad form, since it is exactly the same set of functions as O(n) .

Называть такой скан O(N), сорян, слишком грубо.

Але правильно. Якщо є лінійна залежність від кількості елементів — це O(n). І не важливо чи n/2, чи навіть n/1000000.

всегда существенно меньше N.

Не важливо в скільки чи на скільки менше якщо величина на яку менше константа. Суттєво менше — це O(log n) чи O(sqrt n).

О(1) назвать тоже не могу

Не можеш тому, що час роботи алгоритму не константний і залежить від кількості елементів.

Тут мабуть варто розібратися, що big O нотація означає замість вигадувати якісь O(n/2) чи O(n+1).

Не можеш тому, що час роботи алгоритму не константний і залежить від кількості елементів.

Не зависит он напрямую от количества элементов.
Классика жанра для Trie это О(K) где К — длина ключа, тоесть константа.
Собственно поэтому и хештаблицы частенько пассут задних с их О(1) при вставке и поиске, особенно на больших обьемах данных. С поиском постфиксов ключей не все так просто, но тоже не О(N) и нет прямой зависимости от количества ключей. И не потому что мы остановились сканировать по середине, это какойто частный случай.. Если у нас ключи отсортированы по префиксу, а ищем по постфиксу, то идем до конца дерева. Но этот обход не О(N). Это нужно понимать.

Не зависит он напрямую от количества элементов

Тоді усього два варіанти — або O(1) коли кількість кроків однакова не залежно від розміру колекції, або O(random) — це буде щось нове в CS.

Но этот обход не О(N). Это нужно понимать.

Треба зрозуміти, по-перше, чи залежить час роботи алгоритму від кількості елементів. Якщо ні — це O(1). Якщо залежить — то як само: лінійно — O(n), квадратично чи по логарифму, чи ще який варіант.

Коли ти кажеш «щось середнє між O(1) та O(n)» — це означає складність O(n).

Коли ти кажеш «щось середнє між O(1) та O(n)» — це означає складність O(n).

Это зависит от топологии дерева. Тоесть условно, можно подобрать такую топологию дерева где получим чистый O(n). А можем подобрать другую топологию дерева, где будет О(1).
Топология != Количество ключей. Более того, в многих кейсах мы можем управлять этой топологией и строить именно такое дерево, какое нам удобно (как с контейнером в котором хранятся версии ключей и можно получить срез контейнера (снапшот) на какойто момент времени).

Но в целом я не против. Если ровняем по худшему случаю, то пускай будет

О(N)

Какбы это всеголишь нотация и на конечную скорость работы не влияет.

это всеголишь нотация и на конечную скорость работы не влияет

На швидкість не впливає, але дозволяє оцінити і порівняти різні алгоритми. І чим більше n — тим точніше будуть пропорції.

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

Мені здається ти плутаєш складність та швидкість. Для двох алгоритмів O(n) один може виконуватися 1 мілісекунду, а інший — хоч кілька років. Але те, що вони O(n) говорить нам, що збільшення n пропорційно збільшить час виконання.

І так, чисто з теорії O(1) завжди швидше за O(n), і чим більше n — тим більше різниця. Але це швидкість не у часі, а у кількості операцій на весь набір вхідних даних.

що збільшення n пропорційно збільшить час виконання.

Так в том то и дело. Что на миллион ключей может быть просканировано всего два ключа. И на 100 ключей может быть просканировано 10. Нет пропорциональности. Все зависит от топологии дерева. Вообще давать оценки алгоритмам не такая простая задача как кажется, если это что-то сложнее пузырька или бинарного поиска.

может быть

Не суттєво. Важливо скільки гарантовано — якщо йдеться про пропорційно n (навіть якщо «може бути і менше») то складність буде O(n).

Нет пропорциональности.

Якщо її нема — то це або O(1), або якесь незрозуміле O(random).

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

Ти за цей час міг би почитати про те як складність оцінюють (там не багато) і чим те ж О відрізняється від тета, омега, що таке амортизований час замість вигадувати «між O(1) та O(n)».

Якщо говорити про trie, то його швидкість трохи тупо описувати виключно кількістю елементів (n), бо вставка/пошук геть не залежить від n, тобто дійсно O(1).

Але для trie дуже важливий інший показник — K (довжина ключа в бітах) і B — branching factor (скільки біт на вузол). Тоді вставка/пошук стають O(K/B) а накладні витрати по пам’яті (наче) O(B*n).

edit: хоча фіг його знає як там Бубен свій trie реалізовував, може у нього інша асимптотика. Я писав про класичний спосіб:

struct Node {
  Node* next[1 << B];
  Data* data;
};
для trie дуже важливий інший показник — K (довжина ключа в бітах) і B — branching factor (скільки біт на вузол). Тоді вставка/пошук стають O(K/B) а накладні витрати по пам’яті (наче) O(B*n).

Так, він про це писав вище. І я розумію, що кількість кроків алгоритму пошуку скажімо залежить від довжини ключа, а не від кількості елементів в дереві. Те що я вище написав про колекції взагалі.

Мені здається у випадку trie оцінювати саме найгіршим випадком. А якщо зробити K константою то і до O(1) можна спростити :)

А якщо зробити K константою то і до O(1) можна спростити :)
O(1) still sucks for large values of 1
O(K/B)

Эээ .. и что никого не бомбит ?
Давайте уже признаем, что допускается записывать что-то более точное чем О(1) или О(n) если это имеет смысл в нашем контексте :)

Эээ .. и что никого не бомбит ?
Давайте уже признаем, что допускается записывать что-то более точное чем О(1) или О(n) если это имеет смысл в нашем контексте :)

А почему должно бомбить? :) Контрольный вопрос!

Какова сложность алгоритма для подсчета суммы чисел из двух массивов длиной а и b? :)

int sum(vector<int> &a, vector<int> &b)
  int result = 0;
  for(auto va : a) {
    result += va;
  }
  for(auto vb : b) {
    result += vb;
  }
  return result;
}

O(...) - ? :D

Здесь O(N+M) где N и M количество элементов в векторах а и b.
Здесь констант нет.

Но в примере Юрия

O(K/B)

«B» чистой воды константа. Она может быть например 1, 2 или 8 и всегда постоянна для конкретной имплементации trie.

«B» чистой воды константа. Она может быть например 1, 2 или 8 и всегда постоянна для конкретной имплементации trie.

says who? Без проблем можно реализовать Trie, в котором branching factor переменный, конфигурируется в рантайме (может быть даже разным для узлов разной глубины, если сильно нужно)

Можешь реализовать с переменным.
Только расскажи какая тогда оценка будет ?

O(K/B)

Если B может менятся в рантайме.

O(K/B)

Не катит. Ты даешь общую оценку работы алгоритма, а один и тотже ключ при добавлении может иметь варьированный «B» в рантайме.

Upper bound O(K/B) где B — наименьший B по всем нодам, относящимся к данному ключу.

Ок, тогда я даю оценку своему алгоритму.
О(N*B) где B константа которая всегда больше 0 и меньше 1 и зависит от топологии дерева и природы ключей, также как вверху оценка зависит от бранчинга.

Не можна так.

В тій реалізація, яку показав я, K — параметр структури даних. Тобто грубо кажучи то була не одна структура, а ціле сімейство trie’їв — бери любий. Якщо на C++, то кодом це було б якось так:

template<int B>
struct Node {
  Node* next[1 << B];
  Data* data;
};
тобто немає просто Node, зате є Node<8>.

В ML такі штуки вдало називають гіперпараметрами — тобто перед запуском алгоритму ти фіксуєш деякі «константи» (learning rate, кількість дерев, ...) і тільки потім запускаєш свій алго.

В твоєму ж випадку ти не можеш задати B, тому якось дивно давати оцінку часу в якій фігурує величина, яка тобі геть не підконтрольна («як повезе»).

перед запуском алгоритму ти фіксуєш деякі «константи»
branching factor переменный, конфигурируется в рантайме

Ключове слово «конфигурируется». В твоїй «оцінці»

О(N*B) где B константа которая всегда больше 0 и меньше 1 и зависит от топологии дерева и природы ключей

B просто з’являється, а не опція.

Там ключевое слово рантайм. Тоесть параметр меняется после запуска.

O(K/B)
Эээ .. и что никого не бомбит ?

Разумеется, не бомбит. В определении, которое дал Юрий, B это не константа, а переменная, от которой зависит сложность.

Давайте уже признаем, что допускается записывать что-то более точное чем О(1) или О(n) если это имеет смысл в нашем контексте :)

Дык, запиши что-то более точное. «Меньше чем O(N), зуб даю» это не немного точное, а демонстрация того, что ты сам не понимаешь сколько именно там или понимаешь настолько плохо, что не можешь сформулировать.

ты сам не понимаешь сколько именно там или понимаешь настолько плохо, что не можешь сформулировать.

Я уже сформулировал. Зависит от топологии дерева. Читай, природы ключей. К сожалению мир не чернобелый.

Я уже сформулировал. Зависит от топологии дерева. Читай, природы ключей. К сожалению мир не чернобелый.

Т.е. где-то около O(IT_DEPENDS)

Выращивать решения можешь? Нет? Тогда я впереди тебя.

Я пошутил. У меня мало что есть пока. Только идея (возможно у тебя подсмотренная) и немного кода. Возьмем например алгоритм факторизации. Как одновременно получить несколько тысяч (или больше) непроверенных решений?
Помнишь картинку твою, где дерево растет?
А дальше и того проще — обнаружить ID ветки верного решения в общем русле вывода.

Не хочешь заменить Артема и переписать харрей на раст ? :)

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

Попил кровушки С++ со своими темплейтами, но вроде получилось.
Запилил такой дженерик синтаксис.

HArrayGeneric<std::string, std::string> ha;

ha["dou"] = "hello";

std::string sayHello = ha["dou"];

Работает с любыми типами обьектов, по идее. Вызывает конструктор копирования. Сделал пул обьектов, правда шринки страниц не делал, но они просто делаются поскольку обьекты одного размера на страницах.

Есть сомнения на счет этой строчки, скорей всего это неправильно, но пока что это работает
github.com/...​/src/HArrayGeneric.h#L239

Проблему с непрерывной областью памяти решил следующим образом.
Если это какойто стандартный тип, строка, вектор и тд. То есть стандартные реализации getKeySegments, ничего делать не надо. Если это какойто сложный кастом класс, то нужно сделать свою реализацию getKeySegments. В простейшем случае просто вернуть ссылку на начало своей области памяти и ее размер без байт выравнивания (чтобы в конец ключа не попал муссор).

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

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

insert
getValueByKey
delValueByKey
scanKeysAndValues
Если фанат темплейтов, то можно использовать HArrayGeneric, а лучше по ходу дела его допилить.

У меня вот такая сортировка получилась.
Видео сортировки
На java. А вот ссылка на гитхаб
Кто-нибудь может посмотреть, насколько это вообще полезный софт?
Может я велосипед повторил?
И еще вопрос: как harray с java? Дружит ли?

Тебе нужно сначала понять, твой алгоритм использует доп память или нет.
Если не использует, то тут поле сильно сужается. Классика это квиксорт. И лучшее что пока что придумали это тимсорт. Разница между квиксортом и тимсортом, что тимсорт лучше работает с данными которые уже частично отсортированы. Что в реальной жизни встречается часто. Тимсорт тотже квиксорт, но с вкраплениями шелла на нижних уровнях.

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

Я обмениваю две случайные ячейки, если условия ок ( содержимое соседних ячеек допускает обмен) при этом не уменьшаю размер растущих одноцветных областей.
Правда, код пока сырой, оптимизаций еще вагон можно добавить.
Только вот надо ли оно? Где это применяется? Мне ведь приснилось просто, я и написал. По наитию. Теперь бы найти применение.

На java. А вот ссылка на гитхаб

И как эту свалку рандомных файлов запускать? Сомневаюсь, что кто-то пойдёт в этом копаться.

Выделите нормально код самой сортировки применимо, например, в варианте ${package}.sort(List theArray, Comparator comparator).

Сделайте проект под управлением Maven. Сложите в него пакет с библиотекой и какую-нибудь простую запускалку в духе прочитать int’ы из stdin и выдать результат в stdout.

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

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

Вот это вы верно заметили. Все эти мюоны они для грантов выдумали.
Но токмо Валентин попросил разжевать про хлебушек. Там жеж все криминально просто.
Развернуть зип в эклипс-воркспейс да и того. Run как бы, без параметров. Ну нету мейна у javafx, так ведь не запилили изобретатели.

Развернуть зип в эклипс-воркспейс да и того.

Хм, это уже на что-то похоже. Ладно, попробую по свободе...

На java. А вот ссылка на гитхаб

Сорри но по ссылке куча не читаемого мусора с закоментированным кодом и .java с .class вперемешку....

Кстате к теме Integer. Это интересный вопрос.
В свое время, разработчики еще первых компиляторов, ввели int как стандарт целого числа. После этот стандарт распространился на все языки. Почему они сделали целое число знаковым по дефолту, понятно. Чтобы уменьшить количество ошибок в коде с переполнением. Такая себе защита от дурака. Сделали это ценой того, что потеряли по сути 50% полезных значений в каждой переменной.
Нормальному низкоуровневому хорошо отлаженому коду, не нужен этот ванильный signed int. Он использует везде где это можно только uint32, unsigned int. Ровно так, как целое число хранится в памяти, все 32бита в твоем распоряжении.

Нормальному низкоуровневому хорошо отлаженому коду, не нужен этот ванильный signed int. Он использует везде где это можно только uint32, unsigned int. Ровно так, как целое число хранится в памяти, все 32бита в твоем распоряжении.

Я не согласен, но повторять всю недавнюю дискуссию не хочу.

Пипиши алгоритмы на Rust (где все индексы в массивах и мапах — беззнаковый usize ). Засекай через сколько дней ты завопишь и начнешь требовать старый добрый signed int для индексации.

Засекай через сколько дней ты завопишь

Лолшто. Юзаю только size_t

Похоже, что в С++ тоже беззнаковый тип для индексации, что для меня еще одна причина не юзать С++.

У тебя могут быть массивы отрицательной длины? А комплексная длина для массивов уже тоже возможна, но только после пятой затяжки?

Ви хотіли пошуткувать, але у вас не вийшло

Адресную арифметику никто не отменял.

Который вообще равно определён как signed int

Обычно signed long как минимум (на шибанутой Windows — signed long long), потому что по битности должен быть равен указателю, и давать минимум половину размаха его значений.

У меня почему-то абсолютно все построено на офсетах, смещениях, прыжках по памяти. И почему-то ниразу сходить ниже нуля не понадобилось. Более того, с оверфлоу оно даже как-то поспокойней, сразу крешится. А если сходит тихо на −1 офсет и пойдет дальше, иди потом ищи ошибку.

А у меня нет. Например указатель на данные а мета перед указателем. Например буфер аллоцированный на куче.

Более того, с оверфлоу оно даже как-то поспокойней, сразу крешится

А если я захочу твою штуку использовать в ОСРВ без защиты страниц памяти или вообще на микроконтроллере? :-)

Ирония в том что весь контейнер чуть менее чем полностью состоит из прыжков по памяти по офсетам. Это означает что контейнер на уровне своей песочницы памяти уже работает без защиты страниц памяти. И мне пришлось реализовать свой продвинутый механизм проверки страниц памяти в самом контейнере, который чекает консистентность страниц, дабы отлавливать баги как можно раньше в рантайме.
github.com/...​aster/src/HArray_test.cpp
Получается двойная линия обороны. Базовая от оси, которая чекает ненормальное поведение процесса и селф чек самого контейнера. С таким уровнем двойной защиты, даже если планка памяти случайно сбойнет, харрей имеет средства это обнаружить во время рантайма, во время бенчмарков. Не смотря на весь пц не читаемости кода, это действительно один из самых отлаженных кодов в котором я полностью уверен. И если у меня ошибка в приложении, баг в самом харрее я ищу в последнюю очередь. Потому что баг там сложно найти, даже если там будет миллиард ключей и десять миллиардов джампов по памяти. Все что может прилететь, std::bad_alloc. Память закончилась, но тут уже ничего не поделаешь.

signed int

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

Таких примеров кстате не мало. Вот говнокодеры 60х признались что нулл можно было и не вводить.
www.infoq.com/...​ollar-Mistake-Tony-Hoare

Мне надо было шифтить биты в целых числах, там начались чудеса.

Не знаю что за чудеса, но в любом случае, переходи на Rust на теплые ламповые i32 и u32, где нет никаких непонятнок по поводу того как будет работать тот или иной оператор, все задокументировано без неопределенного поведения.

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

Отрицательные числа тоже целые

на Rust

Си или Раст или Питон, это все безделушки. Хомячки одни и те же идеи переписывают слева направо и справа налево.
Будущее за аспектным программированием. Это самая значимая идея с времён ООП ксерокса и смоллтолка. Просто это пока не очевидно.

Майбутнє за відсутністю програмування як класу. А перед цим ще буде етап розробки систем, які будуть імітувати роботу мозку. Та відповідні мови програмування з’являться для цього.

які будуть імітувати роботу мозку.

"Зачем искусственно выращивать людей, если каждая баба может нарожать их без всякой медицины"© проф. Преображенский

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

Імітація мозку треба для того, щоб потім вчити програми, а не писати їх.

Я вже прийшов до того, що в моєму коді немає явних IF та FOR в так званій «бізнес-лозіці». Та активно використовуються підходи fail safe та fault tolerant. Та все працює роками без змін та помилок, які видні кінцевому споживачеві.

Але аспектне програмування вже вмерло при народженні. За мервячиною немає майбутнього.

непонятнок по поводу того как будет работать тот или иной оператор

Ноги у цього ростуть ще з С де усе було близько до заліза і проци мали різні інструкції для знакових та беззнакових типів.

Нет, всё хитрее. Разные инструкции ни при чём.
В раннем C операции выполнялись буквально и с усечением значений, но так как не у всех процов были отрицательные числа в дополнительном коде, в стандарте была оговорка «а если вы тут получите переполнение, мы не отвечаем за результат». Но все знали, что это только оговорка.
А потом это «джентльменское соглашение» было нарушено, когда авторы компиляторов заметили, что можно начать использовать приёмчики вида: если x — signed, то проверки типа x+1>x автоматически менять на true. Получив на этом выигрыш, не могли уже дальше остановиться.
Для беззнаковых стандарт гарантировал усечение значения, поэтому так хакнуть его не получилось.
(И вот за что я ругаю Столлмана при остальных его безусловных достижениях — что он был первым среди таких абьюзеров стандарта.)

переходи на Rust на теплые ламповые i32 и u32, где нет никаких непонятнок по поводу того как будет работать тот или иной оператор, все задокументировано без неопределенного поведения.

Ну да, просто в debug одно, в release другое.
(Да, я знаю про методы типа checked_add)

Ну да, просто в debug одно, в release другое.

Это то, что мне в Rust не нравится.
Но в защиту Rust — это просто дефолтное поведение, которое конфигурируется на уровне проекта. Если нужно, чтоб в debug и release было одинаковое поведение, это можно указать:

doc.rust-lang.org/...​iles.html#overflow-checks

(Да, я знаю про методы типа checked_add)

Это очень годные методы, и встроены в стандартную библиотеку, что збс. Я знаю, что в С есть разные __builtin_mul_overflow, но камон, куда их засунули это просто ппц. Не сравнить с тем где они лежат в Rust.

Там еще есть unchecked_add для любителей триггернуть неопределенное поведение.

Я знаю, что в С есть разные __builtin_mul_overflow, но камон, куда их засунули это просто ппц.

Это, увы, ещё не стандарт, это GCC расширение, принятое и в Clang.

Там еще есть unchecked_add для любителей триггернуть неопределенное поведение.

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

Если нужно, чтоб в debug и release было одинаковое поведение, это можно указать:

Это хорошо.

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

Еще одна причина переходить на Rust: в Rust нет null

Еще одна причина переходить на Rust: в Rust нет null

Option (его None) это такой же null, только чуть более явный.

Option (его None) это такой же null, только чуть более явный.

Он мягко говоря просто ппц насколько более явный.

Одно дело, когда получаешь Person в Java и не понятно, там что-то лежит или там может быть Null, надо делать проверку или нет?

Другое — когда получаешь Person в Rust, который гарантированно не null, который можно сразу читать. Или Option, что дает вполне определенный сигнал — тут может быть None, и у тебя нет возможности прочитать значение, не сделав проверку и не обработав случай с None.

Одно дело, когда получаешь Person в Java и не понятно, там что-то лежит или там может быть Null, надо делать проверку или нет?

Там уже наделано средств, которые, например, делают проверки — если генератор этой Person не помечен как notnull, то надо проверять, а если помечен, то проверяет честность этой пометки.

Другое — когда получаешь Person в Rust, который гарантированно не null, который можно сразу читать.

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

Person в Java и не понятно, там что-то лежит или там может быть Null, надо делать проверку или нет?

Эмммм, уже давно можно получать не Person, but Optional.

Проблема переполнения ушла в джаве, шарпе, жаваскрипт, а обрезанный инт остался

Проблема переполнения ушла только в Python, Erlang и т.д., где int безразмерный (но и операции с ним стоят как 10-50 обычных). В названных она в полный рост, только решается везде по-разному.

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

signed int это целое.

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

Не было там ошибки, что бы Хоар сейчас ни говорил.
Было отличное решение для того времени, которое помогло справиться со сложностью на десятки лет вперёд.

Засекай через сколько дней ты завопишь и начнешь требовать старый добрый signed int для индексации.

Я для своих проектов делал небольшие врапперы-адаптеры над STL только ради того что бы юзать обычный int для индексов и размеров )

Я там тобі зробив pull request в якому додав cmake — тепер можна генерити ним мейкфайли і проекти для вінди, лінукса та мака.

Спробував додати CI, але чомусь release білд на github крешиться на всіх трьох ОС — github.com/...​ay/actions/runs/988767880.

Глянул комит — много написал

Как ты успеваешь активничать в strava, работать фултайм в FB, заниматься семьей и еще и лячкать в опенсорц? О_о

Там 90% коду згенеровано однорядковими скриптами.

А так — зміна активності лише допомагає. Поки працюю думаю про тренування. Поки тренуюся — думаю про книги, музику, фільми. Поки їм — читаю чи дивлюся щось. Спати страшенно не люблю.

Как ты успеваешь

завязали с Швецией :)

Спасибо за пулл реквест.
По поводу краша.
Везде в коде изменено uint32 на int32_t
С этим есть 2 проблемы.
1. int32_t это integer со знаком, по простому int. uint32 это unsigned int.
Это меняет логику в алгоритме и он крашится.
2. int32_t как и uint32_t определен как
typedef int int32_t;
а это значит что в 32х битном процессе он будет 4 байта, а в 64х битном 8 байт. Это сенситив для логики работы. Всегда должно быть ровно 4 байта (32 бита). Кстате можно переписать и использовать все возможности х64 систем в будущем и получить буст по производительности, сравнивать за раз не 4 байта а 8, но это трудоемкая задача.

Все твои изменения замержил в мастер, но откатил логику с int32_t и убрал креш.
Гуд джоб!

PS: Взялся за дженерик реализацию с темплейтами HArrayGeneric, чтобы писать код в стиле std::map. Думаю до конца недели выкачу первую версию.

typedef int int32_t;
а это значит что в 32х битном процессе он будет 4 байта, а в 64х битном 8 байт.

С чего такое утверждение?
И во всех Unix, и во всех Windows таргетах int — 32 бита, даже если таргет 64-битный.
Вы, наверно, путаете с long. Вот там на 64-битных таргетах 64 бита в Unix, 64 в .NET, но 32 у б-гомерзких извращенцев в Windows C/C++.

Это меняет логику в алгоритме и он крашится.

А что именно меняется?

А что именно меняется?

Там есть шифты битов, подозреваю что они будут по разному работать для int и unsigned int.
Подробнее копать краш смысла нет, поскольку это идеологический вопрос.
dou.ua/...​rums/topic/18849/#2169427

Там есть шифты битов, подозреваю что они будут по разному работать для int и unsigned int.

Ну в общем да. Причём сдвиг знакового влево — UdB, если его считать целочисленным переполнением, а сдвиг вправо — F-деление со знаком.
Увы, это C.

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

Не согласен. Но обсудим там.

Я бачу ти додав sln назад — він не потрібен, його cmake генерить. filters — це взагалі спецефічний для юзера файл.

Мне просто так удобней, сорри.
Я через Винду работаю. У нас на всех проектах есть sln, через make нигде не собирают, хотя наверно есть такая возможность. filters я добавлю в гитигнор.

На вінді так і правда зручніше. Але cmake дозволяє робити проекти та мейки практично для будь-чого просто однією командою. І тоді проекти студії будь-якої версії можна згенерити за секунди коли вони будуть потрібні.

В цілому моє діло запропонувати, ти звісно роби як тобі здається правильно, тут у мене ніяких претензій.

Мне просто так удобней, сорри.

Попробуй cmake освоить
Забудешь про ручные проекты студии в большинстве случаев

Если у тебя есть кастомные настройки проекта, например debug home folder или что то еще, это можно сохранить в файле .filters (вроде так) и хранить его в своем гите для настройки

Обернешь генерацию проекта в скрипт, который и проект под студию сгенерирует, и папки дебага с конфигами создаст. Старт проекта должен быть в 1 клик мышкой! =)

Здесь несколько человек возмущалось, что у автора читерские бенчмарки, где он сравнивает с коллекциями, у которых совершенно другие цели и функциональность.

Так вот, предлагаю автору to pick on somebody your own size и пробенчмаркать с чем-то похожим. Например: github.com/Tessil/hat-trie (первое что выдал гугл на fast trie)

Заодно и посмотришь, как эту хрень завернули в нормальный юзер френдли контейнер

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

лол, а с стдмапой корректно?

Да, потому что она тоже содержит сортированных данные и предоставляет интерфейсы поиска по диапазону.
В моей СУБД харрей может использоваться как движок для индекса, как и бинарные деревья. Хештаблицы — нет. Они для аналитических запросов не катят.

в обычных субд я могу построить индекс на числах с плавающей точкой. В мапу тоже могу их присунуть. А вот в harray чет не могу.

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

в обычных субд я могу построить индекс на числах с плавающей точкой. В мапу тоже могу их присунуть. А вот в harray чет не могу

Можешь. Это ещё одно отличие взрослой имплементации от академической, которая работает только со строками.

//Set float comparator for right sorting
//Another options: setStrComparator, setInt32Comparator, setUInt32Comparator
//or define your custom comparator through setCustomComparator
ha.setFloatComparator();

Глянул код по диагонали. Они темплейты вроде как реализовали только для строк и примитивных типов. Моя мапа работает с любыми бинарными данными, не только с строками. Поэтому хотелось бы более универсальное решение с шаблонами

А кто стандарты С++ хорошо знает ?
Хочу написать такого плана метод.
Какой абстрактный тип здесь должен быть вместо Т ?

void CopyFunc(T obj)
	{
		char arr[1000];

		std::copy(obj.begin(), obj.end(), arr);
	}

Это ж С++.

Делай шаблюнную функцию и просто фигач T без указания типа.

Ок, а как сделать развилку ?
Если обьект имеет методы begin, end то в if, если не имеет то в else ?

Смысл если Т поддерживает итератор, читать данные в буфер через итератор, иначе через адресс обьекта в памяти

void CopyToBuff(T obj, char* buff)
{
       if(HAS_ITERATOR(T)
	{
                  std::copy(obj.begin(), obj.end(), buff);
        }
       else
        {
                  for(int i=0; i<sizeof(T); i++)
                          buff[i] = (char*)&obj[i];
        }   
}

Тебе нужно 2 функции. Сложное, но надежное решение — это вывернуться через SFINAE с std::enable_if, определив что переданный контейнер Т может быть проитерирован через begin/end. Готового енейблера нету, прийдется написать велосипед. На stackoverflow народ уже решал эту проблему, поищи. Разные решения предлагают.

Простое и ненадежное решение перегрузить 2 функции:


// Example program
#include <iostream>
#include <string>
#include <vector>

template<typename T>
void CopyToBuff(T obj, char* buff)
{
    std::cout << "generic pointer\n";
}

template<typename C>
void CopyToBuff_STL(const C& obj, char* buff)
{
    std::cout << "STL generic\n";
}

template<typename T>
void CopyToBuff(const std::vector<T>& obj, char* buff)
{
    CopyToBuff_STL(obj, buff);
}

int main()
{
    struct Foo {};
    Foo object;
    char buffer[42];
    
    CopyToBuff(object, buffer);
    
    std::vector<int> anotherObject;
    CopyToBuff(anotherObject, buffer);
}
Ненадежное потому что если попытаться скормить list, а перегрузки нет — то вызов пойдет в версию которая generic.

Можешь подсказать, в чем тут может быть дело ?
Есть простейший класс. Почему всегда и на set и на get вызывается одна и таже ф-ция ?

template <typename K, typename V>
class Array
{
public:
	const V& operator[](std::size_t idx) const
	{
		V v;
		return v;
	}

	V& operator[](std::size_t idx)
	{
		V v;
		return v;
	}
};

int main()
{
	Array<int, int> arr;
	arr[0] = 1;     //V& operator[](std::size_t idx)
	int x = arr[0]; //V& operator[](std::size_t idx). Why not const V& operator[](std::size_t idx) const ?
}

Если я правильно помню, в C++ у оператора [] нет понятия get/set. Это функция, которая возвращает ссылку на какое-то значение. Если ты пытаешься сделать get, ты получаешь эту ссылку и что-то с нее читаешь. Если ты пытаешься сделать set, то ты записываешь новое значение по этой ссылке.

Разница между const/не const состоит в том, что по конвецнии значение, которое объявлено как const, нельзя изменять. То, которое не объявлено как const изменять можно.

В твоем случае Array<int, int> arr; не объявлен как const, поэтому в обоих случаях вызывается non-const реализация оператора.

Тяжело понять логику С++ разработчиков.
Получается нужно писать гибридный метод insertOrGet. Который будет инсертить и возвращать ссылку на велью если такой ключ не существует. И если ключ существует, то будет возвращать ссылку на уже существующее велью.
Это замедлит работу. Потому что insert != get. Я думаю замедление будет в районе 10-15% только из-за слоупоков которые не смогли продумать базовый нормальный сценарий перегрузки операторов в С++ (кстате в Шарп с этим все уже нормально)

Ну не уверен что 10-15%. Константность все равно можно снять. Либо не снимать, а втупую прочитать память. Насколько мне известно это не тот модификатор (const) который позволяет компилятору оптимизировать код.
Поэкспериментируй с godbolt.org

#include <cstdlib>

struct vector3f {
    vector3f() {
        v[0] = rand();
        v[1] = rand();
        v[2] = rand();
    }

    float v[3];

    float& operator[](size_t i) {
        return v[i];
    }

    const float& operator[](size_t i) const {
        return v[i];
    }
};

int main(int argc, char ** argv)
{
    vector3f v1;
    const vector3f v2{};

    int a = v1[argc];
    int b = v2[argc];

    return a + b;
}
Вот такой примитивный код или идентичный ассемблер выдает или с разницей в 1 инструкцию

Еще можно экспериментировать с тем же самым, только main поменять на

int main(int argc, char ** argv)
{
    vector3f v = vector3f{};
    int a = v[argc];
    return a;
}
и вставлять/убирать const. Компилятор иногда оптимизирует изза наличия двух переменных.

Это хорошо работает с вектором, массивом и тд. Когда операция Get == Insert/Update. А теперь представим что под капотом что-то сложнее, например обычный однонаправленный связной список. Получается операция insert, может быть за О(1), если мы будем хранить хвост списка. А операция поиска О(N) поскольку нужно бежать по всему списку с самого его начала.

Это глупое решение разработчиков С++. Которые простейшую операцию сделали неочевидным способом и заточили ее под случай
Get == Insert/Update без всякой веской причины, что неверно в многих других случаях.

Ну тогда разноси на несколько методов get/insert/update
Будет single responsibility в классическом его виде )

Сейчас так и есть :) Но хотят же чистый ванильный синтаксис с темплейтом [ ]
Чтобы писать в таком няшном стиле.

HArray <int, int> arr;
arr[0] = 1;
Тяжело понять логику С++ разработчиков.
Получается нужно писать гибридный метод insertOrGet. Который будет инсертить и возвращать ссылку на велью если такой ключ не существует. И если ключ существует, то будет возвращать ссылку на уже существующее велью.

Да. Потому что [] это наследие массивов.
Для более прямо определённых операций типа «проверить есть ли такое», «вставить с защитой от дублирования» и т.п. — есть свои отдельные названия.

Посмотрите на интерфейс стандартного std::map.

Там нижче правильно сказали про масиви. Подивись на std::map::at() як альтернативу.

Тяжело понять логику С++ разработчиков.

я вот купил другую книгу, чтоб понять, буду читать:
www.amazon.com/...​_asin_title?ie=UTF8&psc=1

Получается нужно писать гибридный метод insertOrGet. Который будет инсертить и возвращать ссылку на велью если такой ключ не существует. И если ключ существует, то будет возвращать ссылку на уже существующее велью.
Это замедлит работу. Потому что insert != get. Я думаю замедление будет в районе 10-15% только из-за слоупоков которые не смогли продумать базовый нормальный сценарий перегрузки операторов в С++ (кстате в Шарп с этим все уже нормально)

Можно посмотреть, например, тот же std::map и найти, что там есть методы для выполнения всех кейсов, а именно:

at
[]
insert
insert_or_assign
emplace
erase
find

тысячи их

arr не константная переменная
Подробно описано в „16.3 Overload resolution” www.open-std.org/...​ocs/papers/2017/n4713.pdf , в частности 16.3.1.2

The set of candidate functions can contain both member and non-member functions to be resolved against
the same argument list. So that argument and parameter lists are comparable within this heterogeneous
set, a member function is considered to have an extra parameter, called the implicit object parameter, which
represents the object for which the member function has been called. For the purposes of overload resolution,
both static and non-static member functions have an implicit object parameter, but constructors do not.

Насколько я понял написанное , arr[0] эквивалентно вызову
operator[](arr, 0).
А таких operator[] будет 2:
operator[](const Arr&, size_t)
operator[](Arr&, size_t)
Вот он и выбирает по best candidate.

Бубен, ты полез в дебри, в которые даже я бы лезть не стал.

Это хорошая идея — каждый объект это просто блок памяти, который можно скопировать. В реальности в С++ это все совсем не так, как ты предполагаешь и интерпретировать объект просто как блок памяти нельзя.

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

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

Например, если тебе передадут shared_ptr (умный указатель с счетчиком ссылок), и ты его сокопируешь побайтно, ты создаешь новую ссылку на внутренние данные, не увеличив счетчик ссылок. В определенный момент счетчик ссылок дойдет до 0 и память будет освобождена, но в твоей мапе так и будет лежать неучтенная ссылка на эту памяти и кто-то может ее получить и обратиться к этой памяти (aka dereference dangling pointer), что в С++ является неопределенный поведением.

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

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

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

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

После этого ты вызываешь copy или move конструктор.

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

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

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

Представь себе, ты сидишь на стуле. Тебя кто-то хочет посадить на другой стул. Вместо того, чтоб попросить тебя «Бубен, сядь пожалуйста на вот тот стул», берут пилу, распиливают тебя на куски, сливают кровь в ведро, отностят куски к новому стулу, склеивают изолентой, заливюат кровь обратно. Физически это тот же Бубен, но он уже немножко не такой как был раньше. Когда ты закричишь «Что вы делаете! Прекратите меня резать», тебе скажут — «Слушай почему кричишь? Мы вот вчера фигурку из пластелина так же разрезали, перенесли на новое место и склеили — посмотри, сидит как новенькая».

Есть куча причин почему это делать нельзя.
Примеры:
self-referential classes (одно из полей класса ссылается на другое поле. При перемещении этого объекта в памяти нужно поля обновить, чтоб они ссылались в новое место в памяти)
Смарт поинтеры (при перемещении нужно или обновлять счетчики или инвалидировать старые указатели)
Объекты, у которых копирование/перемещение запрещено. Двигать такие объекты в памяти или копировать куда-то вообще нельзя.

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

Правильный каноничный способ это делать — как тебе тут я и Олександр пытаемся объяснить. Можешь еще залезть в потроха того же std::unordered_map или std::vector чтоб понять как там сделано и попытаться воспроизвести.

Ты натягиваешь свое знание С или очень древнего С++ на современный C++, в котором все по-другому.

Если хочешь осознать уровень п****ца и понять почему от С++ надо держаться подальше и оставаться на старом добром С (или переходить на Rust), почитай:

www.amazon.com/...​_asin_title?ie=UTF8&psc=1
www.amazon.com/...​_asin_title?ie=UTF8&psc=1

Дауж. Такая простыня комента с выжимкой

залезть в потроха того же std::unordered_map

И самому разбираться.
Спасибо.

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

Есть причины по которым С++ имеет репутацию ипанутого языка, который нельзя выучить за 21 день, смекаешь?

репутацию ипанутого языка

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

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

Все, что ты можешь хранить в общем случае — это так называемый «trivial type» — скалярный тип, не имеющий конструкторв, деструкторов, без наследования и т.п. Поищи is_trivial тут: en.cppreference.com/w/cpp/types/enable_if

По иронии даже std::string не является trivial, тебе нужно будет написать несколько специализаций на нетривиальные типы (которые все равно могут быть безопасно представлены как набор байт).

Этот врапер написать невозможно

Завтра подумаю можно ли обойти эту проблему через какой-то трюк.

Подумай еще об этом:

В сложных структурах с несколькими полями будет место, которое зарезервировано для выравнивания полей (aka padding). В этом padding лежит мусор.

Если ты напрямую переводишь значение в последовательность байт с помощью memmove, ты скопируешь и этот мусор и вставить его в свою мапу. Это создаст проблему — ключи, которые логически идентичны (если сравнивать значения полей) могут иметь разное представление в памяти за счет мусора в padding. Поскольку твой код не отличает padding от самих полей, возможна ситуация, когда мы вставили ключ в твою мапу, а потом пробуем что-то извлечь по тому же ключу (но уже с другим мусором в padding), но она ничего не найдет.

Подробнее: wiki.sei.cmu.edu/...​ not compare padding data

Надеюсь, ты сможешь заснуть с этим заннием.

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

вот value теоретически может быть любым обьектом, да

Трай — это структурка для строк

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

Нет никаких мат препятствий хранить любой список байт

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

Объекты можно в пуле хранить, не проблема. Проблема с ключами. Как дженерик тип ключа преобразовать в набор байт, чтобы этот ключ запихнуть в мапу

зачем такое делать, ведь поиск по префиксу и итерация потеряют смысл, и ты скатишься до обычного key-> value? а так то да, можно хрвнить в пуле, брать от каждого обьекта md5 и пихать его как ключ

чем может быть мне полезен копи конструктор

Тим, що в С++ це єдиний спосіб правильно скопіювати об’єкт.

Если обьект имеет методы begin, end то в if, если не имеет то в else ?

Дві різних реалізації. Напиши чи візьми з якоїсь ліби is_iterator, щось типу stackoverflow.com/...​trary-type-is-an-iterator.

Не певен, що правильно зрозумів твоє питання. Щось таке:

template <class T>
void CopyFunc(const T& obj) {
  vecor<T> arr;

  std::copy(obj.begin(), obj.end(), arr.begin());

А вот и Монады подвезли.
Классический пример монадической функции с шарпа.

var dic = new Dictionary<string, List<int>>();
//fill dictionary
IEnumerable<int> joinAllListsIntoOne = dic.SelectMany(x => x.Value);

В харрей это все работает бай дизайн, без каких либо Linq костылей.
И работает за O(N) где N количество элементов в списках, по которым бежит итератор
scanKeysAndValues

Если продолжить идею монад, например заджойнить не все списки, а только ключи которые начинаются на StartKeyFromPattern

var dic = new Dictionary<string, List<int>>();
//fill dictionary
IEnumerable<int> joinAllListsIntoOne = dic.Where(x => x.Key.StartsWith("StartKeyFromPattern")).SelectMany(x => x.Value);

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

Ти дуже хитро все це звів до unit32 :) А з std::string так зможеш? Чи просто з якимось невідомим типом T?

PS. Промазав з коментом — це відповідь до написаного тобою нижче.

Вот врапер который полностью универсальный. Принимает в качестве ключа любой массив байт и в качестве велью любой массив байт.
github.com/...​aster/HArray/HArrayChar.h

пример использования

HArrayChar ha;

	ha.insert("a", 1, "b", 1);

	char value[16];
	uint32 valueLen = 0;

	ha.getValueByKey("a", 1, value, valueLen);

Все тоже самое, но с std::string

HArrayChar ha;

	std::string key = "a";
	std::string val = "b";

	ha.insert(key.c_str(), key.length(), val.c_str(), val.length());

	char value[16];
	uint32 valueLen = 0;

	ha.getValueByKey(key.c_str(), key.length(), value, valueLen);

	value[valueLen] = 0;

	std::string outVal(value);

Пример немного кривоватый, делает лишнее преобразование в конце. Но при желании сможешь написать свой врапер HArrayString.h на основе HArrayChar который будет принимать строго интерфейсы std::string

Так, але знову ж таки тут зручно те, що string можна звести до char[], а той в свою чергу є просто буфером. Але таке не буде працювати з довільними типами ключа та значення і доведеться писати врапери для кожної комбінації типів і в них робити ці перетворення між типом та масивом байт. А це стає особливо складно коли треба буде глибоке копіювання робити.

В той же час map працює для будь-якого типу для якого визначені конструктор по замовчанню та конструктор копіювання хоча б.

Тобто твій враппер мав би виглядати приблизно так:

template <class Key, class Value>
class HArray {...};

До речі я не хочу сказати, що твоя реалізація не робоча — вона просто для інших сценаріїв і робить акцент ключах та швидкому доступі до них. В той час як контейнери STL повністю абстрагують від цих деталей і дають всі необхідні механізми з коробки.

Честно говоря до сих пор не понял почему нельзя темплейты с++ натянуть на харрей.
Я бы это и сам сделал, просто в моих задачах мне не надо.

до сих пор не понял почему нельзя темплейты с++ натянуть на харрей

Можна, але тобі для цього треба мати:
— універсальну хеш-функцію для довільного типу, або спеціалізовані хеш-функції. Це щоб значення типу K перетворити в uint32.
— використовувати для значень типу T конструктори T(), T(const T&), T(T&&), деструктор ~T() та оператори operator=(const T&), operator=(T&&).
— додати ітератори
— додати підтримку алокаторів

Я бы это и сам сделал, просто в моих задачах мне не надо

Я розумію, що ти вирішував іншу проблему. Але тоді порівнювати з std::map недоречно — порівнюй з int[].

універсальну хеш-функцію

Зачем мне хешфункция ? Зачем ее реализовывать ? С++ темплейты требуют ее реализации ? Можешь заимплементить и вернуть там ноль, я ее никогда не буду вызывать внутри мапы.

Зачем мне хешфункция ?

Щоб значення типу T перетворити в індекс.

Зачем ее реализовывать ?

Щоб користувач твого коду не мав її писати сам для кожного типу.

С++ темплейты требуют ее реализации ?

Темплейти тут ні до чого. Ти порівнюєш з std::map та іншими подібними структурами, а для їх використання все є «з коробки» і мені не треба «написати простенький пул» щоб перетворювати T в uint32.

Щоб значення типу T перетворити в індекс

Зачем ?

Щоб користувач твого коду не мав її писати сам для кожного типу.

Зачем ?

і мені не треба «написати простенький пул» щоб перетворювати T в uint32.

Тебе не нужно писать пул. Я тебе написал врапер у которого инсерт.
insert(char* key, int keyLen, char* value, int valueLen). Сюда можно запихнуть любой объект как ключ и любой объект как значение ровно в одну строчку кода.
Единственное ограничение что ключ и значение не более 900 байт. Но если кто-то реально упрется в это ограничение в своей задаче я потрачу время и сниму его.

Зачем ?

Щоб шукати за ключем виходило швидше ніж O(n). Інакше можна простим масивом скористатися.

insert(char* key, int keyLen, char* value, int valueLen)

Такий код зараз треба писати для кожного можливого типу. В той час як map працює з будь-яким типом ключів і значень для яких виконуються умови згадані вище.

з будь-яким типом ключів

С каким будь яким. Возьмём простейший char*. std::map с ним не работает нормально. Вообще с любым типом который представлен как указатель на объект не работает без 100 приседаний . Стоит ли говорить что в Си указатели чуть менее чем везде

Возьмём простейший char*. std::map с ним не работает нормально.

Працює. Але якщо тобі треба щоб значення порівнювалися як рядки, а не за адресою — тут і треба свій компаратор мапі давати.

с любым типом который представлен как указатель на объект не работает без 100 приседаний

Вказівники дуже легко обертати в якийсь shared_ptr і це вирішує велику кількість проблем. Сирі вказівники — їх краще в С++ взагалі не використовувати.

в Си указатели чуть менее чем везде

Якщо ти зводиш все до С то і з std::map порівнювати не варто. Порівнюй з uint32[] - ця структура буде швидше за твою.

Тебе не нужно писать пул. Я тебе написал врапер у которого инсерт.
insert(char* key, int keyLen, char* value, int valueLen). Сюда можно запихнуть любой объект как ключ и любой объект как значение ровно в одну строчку кода.

Збс, можно, например, запихнуть value типа std::vector? А, подожди, мне его надо к char* кастить? Можно пример кода, который это делает?

Не можешь вектор привести в массив байт, которым он по сути является ?
Погугли.

ты сказал, что можно запихнуть любой объект как значение. Покажи как запихнуть

vector < bool >

(char*)&myVector.

Оно ?
Вектор непрерывный массив байт. Получаем адресс и кастим.

(char*)&myVector.

Оно ?

Мне нравится в каком направлении ты мыслишь, но все же, можно полный пример, который вставляет вектор в твой trie в качестве значения?

Я не могу выполнять роль Гугла за тебя. Сорян. Для меня достаточна аксиома что любой объект в памяти это массив байт. Для харрея этого достаточно. Есть адресс в памяти и количество байт, вставляй ключ и значение.

Т.е. ты понимаешь, что любой объект в твою trie вставить в качестве ключа невозможно, и ты ввел людей в заблуждение? Ок.

Если объект не представлен в памяти как непрерывный массив байт и не может быть преобразован в непрерывный массив байт, то вставить невозможно как ключ. Но я о таких объектах не знаю. Может они у тебя на флопи диске живут в битых секторах, я хз если честно

Объект простой:

    std::vector<bool> my_vector { true, false, true };

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

А если я тебя буду просить 2+2 прибавить. А потом 2+3. А потом 3+2 в четыре утра в моей тайм зоне ?
Можешь как слив засчитать.

Если объект не представлен в памяти как непрерывный массив байт и не может быть преобразован в непрерывный массив байт, то вставить невозможно как ключ. Но я о таких объектах не знаю.

Будь-який об’єкт типу з інкапсульованими вказівниками чи посиланнями.

До того ж якщо в об’єкті є хендлери (наприклад на файл чи UI-ресурс) то копіювати значення хендлера не вірно — треба заново отримувати ресурс. А зробити це без конструктора копіювання буде дуже складно.

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

Какой поинт в том, чтоб сравнивать структуру, которая не поддерживает range запросы со структурой, которая их поддерживает?

Сравни с вот этой, например:

doc.rust-lang.org/...​TreeMap.html#method.range

Значит ты до сих пор не понял как работает Trie.
Сканы по диапазону есть и они даже эффективней работают чем в TreeMap.

Вот тебе четыре ключа
1 1 1 1 1
1 1 1 1 2
1 1 1 1 3
1 1 1 1 4
При скане диапазона с 2 до 3 харрей прочитает 6 чисел. TreeMap 15.

github.com/...​tKeysAndValuesByRange.cpp

Значит ты до сих пор не понял как работает Trie.
Сканы по диапазону есть и они даже эффективней работают чем в TreeMap.

— Кококо, в хеш-таблице нет скана ключей по диапазону
— Разумеется, нет. Если тебе надо поиск по диапазону, то вот тебе TreeMap, которая позволяет поиск по диапазону
— Кококо, TreeMap это не Trie!

Вот тебе четыре ключа
1 1 1 1 1
1 1 1 1 2
1 1 1 1 3
1 1 1 1 4
При скане диапазона с 2 до 3 харрей прочитает 6 чисел. TreeMap 15.

1. Я не знаю что такое «прочитает X чисел» и почему меня должно это волновать.
2. Твоя trie делает поиск по подстроке? В классической реализации trie поиск возможен только по префиксу, т.е. если тебе нужно где-то найти 2 внутри ключа, тебе все равно прийдется сканировать все ключи от начала до конца.

И в чем смысл твоего поста ?
Хештаблицы работают и медленнее и ничего не ищут по подстройке, но интонация как будто это плюс.
Да, трай ищет только по префиксу ключа. А TreeMap что уже в регекспы без фулскана научился ? В чём твой принт ?
И ещё раз. У меня на гите есть обучающая статья с разноцветными картинками для самых маленьких, чтобы они наконец поняли почему трай сканирует по диапазону лучше бинари три. Да и мой пост с монадами должен был навеять мысли. Ссылку я тебе присылал.

И в чем смысл твоего поста ?

А в чем смысл твоего поста?

Хештаблицы работают и медленнее и ничего не ищут по подстройке, но интонация как будто это плюс.

Не медленнее, а быстрее, бенчмарки уже провели

Да, трай ищет только по префиксу ключа. А TreeMap что уже в регекспы без фулскана научился ? В чём твой принт ?

ты выше намекнул, что твоя Trie сомжет найти 2 внутри ключа без сканирования всех ключей. Если ты пытался что-то другое сказать, сформулируй попонятнее, плиз.

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

Если прочитать твою «обучающую статью», то читатель как раз прийдет к выводу, что Trie структура сканирует хуже кроме некоторых вырожденных случаев. Чтоб Trie стал маргинально лучше, нужна очень грамотная реализация с кучей нетривиальных оптимизаций, и пока что нет оснований считать, что мы имеем дело с таковой, так как автор не может объяснить свой алгоритм дальше трех картинок из textbook.

Не медленнее, а быстрее, бенчмарки уже провели

Можно ссылку на твои бенчмарки ?

Trie структура сканирует хуже кроме некоторых вырожденных случаев

Можешь объяснить почему хуже ?

так как автор не может объяснить свой алгоритм дальше трех картинок из textbook.

Артёмка, ну какие ещё документы тебе писать. До тебя три разноцветные картинки даже не дошли. Ты только что для себя открыл что трай может искать по диапазону ключей. Это уже прорыв я считаю.

Можно ссылку на твои бенчмарки ?

Ниже в этом топике

Можешь объяснить почему хуже ?

Легко. Книжная реализация Trie «в лоб» будет неэфективной с точки зрения cache locality — в худшем случае при поиске одного ключа будет получать cache miss на каждый символ в ключе без шансов на speculative memory fetch.

Артёмка, ну какие ещё документы тебе писать. До тебя три разноцветные картинки даже не дошли. Ты только что для себя открыл что трай может искать по диапазону ключей. Это уже прорыв я считаю.

Для меня писать ничего не нужно, напиши хотя бы для себя.

Ниже в этом топике

Я знаю только один бенчмарк где ты сдул. При этом то была хештаблица, которую тюнили передачей капасити, которая конечно ничего не ищет по диапазону.
Или ты о другом бенчмарке ?

Легко. Книжная реализация Trie «в лоб» будет неэфективной с точки зрения cache locality

Книжная реализация на 50 строк кода без патриции и вот этого всего действительно будет неэффективной. Но какое это имеет отношение к моей реализации на 8000 строк кода ?

Для меня писать ничего не нужно, напиши хотя бы для себя.

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

Книжная реализация на 50 строк кода без патриции и вот этого всего действительно будет неэффективной. Но какое это имеет отношение к моей реализации на 8000 строк кода ?

1. Какая разница сколько там строк кода?
2. Я не знаю какое отношение она имеет к конкретно твоей реализации. Ты зачем-то выложил ее в раздел документации в свой гитхаб, а теперь говоришь, что то документация не на твою trie? Выложи документацию на свою trie тогда, будет что почитать.

Выложи документацию на свою trie тогда, будет что почитать.

Открытый исходный код лучшая документация. Бенчмарки лучший арбитр на все твои догадки про кеш миссед. Код дебажится на раз два. При желании можно потратить недельку и во всем разобраться. Можешь начать с HArrayInt. Он вообще простой как табуретка, там не более 300-500 строк кода.

Открытый исходный код лучшая документация.

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

Код дебажится на раз два.

Сенкс, но я дебагером за последние 5 лет пользовался может раза три, и делать это еще раз ради того, чтоб разобраться в корявом С++ коде я не буду.

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

В коде хватает комментариев. Не бойся, глаза боятся руки делают.

дебагером за последние 5 лет

Мсье пишет без багов. Занятно.

дебагером за последние 5 лет
Мсье пишет без багов. Занятно.

lemire.me/...​/i-do-not-use-a-debugger

Linus Torvalds, the creator of Linux, does not use a debugger.
Robert C. Martin, one of the inventors of agile programming, thinks that debuggers are a wasteful timesink.
John Graham-Cumming hates debuggers.
Brian W. Kernighan and Rob Pike wrote that stepping through a program less productive than thinking harder and adding output statements and self-checking code at critical places. Kernighan once wrote that the most effective debugging tool is still careful thought, coupled with judiciously placed print statements.
The author of Python, Guido van Rossum has been quoted as saying that uses print statements for 90% of his debugging.

Это потому что на Линукс дебаг это боль и страдания, по сравнению с вижуал студио. Пускай сами принтами дебажат как в прошлом веке.
Ну и

for 90% of his debugging.

Подразумевает не 3 раза за 5 лет.

Пускай сами принтами дебажат как в прошлом веке.

Ну взагалі то в *ніксах давно є gdb та різні графічні надбудови.

2 Artyom Krivokrisenko, Oleksandr Golovatyi, Punk Floyd

Да здраствуют враперы.
Имплементация которая сохраняет велью произвольной длины
(но не более чем MAX_CHAR-CONTENT_ONLY_TYPE, что не более 900 байт в текущей версии. Не спрашивайте меня почему так, можно пофиксить потом :) )
github.com/...​/HArray/HArrayLongValue.h

Имплементация которая сохраняет value как ValueList в котором каждое значение уникально. Здесь без ограничений.
github.com/...​ArrayUniqueIntValueList.h

Вообще мне нравится ход мысли в проектировании. Тру пацаны теперь используют олдскульные интерфейсы и получают околосветовую скорость. Для ленивых, перекладываем имплементацию листов, алокацию памяти, хранение произвольных строк в велью на харрей используя враперы, которые чуток замедляют харрей, но не критично. Главное что все работает в стройной математической модели.

Упс, мій комент вище був саме до цього.

А хотите пацаны фокус. Меня уже неоднократно просили добавить функциональность, чтобы мапа сохраняла не 32х битные (4 байта) value, но value произвольной длины.

А теперь следите за руками, вы должны прочуствовать всю красоту игры, насладится всем изяществом Trie в имплементации HArray.

Итак, шаг первый.
1. Мы выбрасываем Value, он нам больше не нужен. Выбросить Value в задаче где была необходимость сохранять Value произвольной длины ? Начало неплохое.
2. Далее, в конец ключа мы встраиваем Value и получаем просто более длинный ключ.
Например если ключ 1 2 3 5 а велью 7 8 9 то ключ теперь 1 2 3 5 7 8 9 а велью нет.
3. Поиск ключа это теперь поиск по шаблону,
github.com/...​tKeysAndValuesByRange.cpp
который алгоритмически по скорости равноценен извлечению ключа. Разница в том, что в конце мы сканируем поддиапазон хвостов ключей. Если мы сохраняли одно велью, то поддиапазон будет из одного велью.

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

1. Мы не написали ниодной новой строчки кода. Вин.
2. Мы получили струкутуру которая аналогичная

//если нужно хранить только одно значение, это List с одним значением. Лиспу привет!
map<key with variable len, List<value with variable len>> 
Мапа заимплементила List который теперь хранится как value. А ведь это самый ходовой сценарий для мапы. Банальный индекс это Ключ и список айдишников. Вот это поворот !
3. Но это еще не все. В этот List теперь невозможно добавить дубликат. Более того, проверка на наличии дубликата реализована на скоростях HArray ©
4. А теперь пошла фантастика. Value с одинаковыми префиксами в таком List сжимаются !
Wat ??
5. И удаляются из списка List по всем кананонам, как говорится
dou.ua/forums/topic/33788

Теперь вы понимаете, что хештаблицы и всякие бинарные деревья, по своей задумке просто муссор по сравнению с структурами вроде HArray. Да, так бывает, это как с числом Пи.
2 тыщи лет люди уточняли число Пи через многоугольники. А потом пришел Ньютон и нашел путь просчитать все на листике за несколько дней. Он получил результат, на который у другого ученного ушло 20 лет кропотливых вычислений.

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

PS: Если ты был внимательным читателем, то скорей всего у тебя появился вопрос о коллизиях. Другими словами ключ 1 2 3 4 с велью 5 6, будет таким же как ключ 1 2 3 4 5 с велью 6. Да, есть такая проблема, но она не везде акутальна и может быть решена. Нет ничего невозможного :)

А теперь вопрос на сотню литкод задач.

Если ты был внимательным читателем, то скорей всего у тебя появился вопрос о коллизиях. Другими словами ключ 1 2 3 4 с велью 5 6, будет таким же как ключ 1 2 3 4 5 с велью 6

Как не меняя код и не внося в него изменения решить просто и изящно эту проблему. Мапа у нас хранит только ключи и значения. Этих входных данных для решения задачи достаточно.

ПС: А я говорил что код (почти) идеален. Теперь он часто нами управляет а не мы им. Если у нас есть задача и мы не знаем как ее решить, то это ещё не факт что она уже решена там без нашего ведома ))

А теперь вопрос на сотню литкод задач.

Или на 5 минут для студента 2-го курса толкового вуза, по крайней мере в основных подходах.

Другими словами ключ 1 2 3 4 с велью 5 6, будет таким же как ключ 1 2 3 4 5 с велью 6

Берём условие Фано и понимаем, что если в ключе возможны все значения байт, то вставить новое значение как терминатор не получится. Или у тебя байт 0 не разрешён? Тогда всё банально — просто склеиваются две NUL-terminated строки.
Но если разрешён, то есть два базовых подхода: префикс длины и escape-последовательности. Оба работают. Первый заметно эффективнее, но требует лёгкой модификации функции сравнения. Могут быть вариации типа сборной строки из чанков.
Не хочу лезть в код, смотреть, что ты там сотворил, но если подход не соответствует одному из этих, то можно будет найти нарушение разделения.

Хороший план, но все немножко проще.
Помните я писал

1. Мы выбрасываем Value, он нам больше не нужен.

Разве может быть идеальной картина где есть что-то лишнее ?
Так вот, Value возвращаем. Мы там будем хранить длину нашего Value.

При сканировании добавим проверку и вуаля, коллизий больше нет :)
github.com/...​ray/HArrayLongValue.h#L41

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

ключ 1 2 3 4 с велью 5 6, будет таким же как ключ 1 2 3 4 5 с велью 6

Фиксить это довольно просто. Нужно еще удлинить ключ на один сегмент.
Теперь композитный ключ будет состоять из 3х сегментов.
1 2 3 4 сам ключ + 5 6 велью + 2 длина велью в нашем ключе => Value которое всегда 0.

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

Все есмЪ ключ друзья, канонический, триединый из трех сегментов — философский вывод. Пофиксил код врапера.

Теперь композитный ключ будет состоять из 3х сегментов.
1 2 3 4 сам ключ + 5 6 велью + 2 длина велью в нашем ключе => Value которое всегда 0.

Хранение длины в конце это таки красивый трюк, отлично.

Кстате интересный вопрос. Вот мы взяли существенно увеличили длину ключа.
Допустим если ключ был всего 8 байт, а значение было 256 байт, то длина ключа увеличилась до 8 + 256 + 4 = 268 байт. На первый взгляд кажется что это сильно ударит по производительности, с таким то длинным ключем. Но правильный ответ — нет.
Дело в том что больше всего бьют по производительности сильно ветвлящиеся ключи. Например SEQUENCE последовательности ключей, это худший сценарий, где каждый раз мы попадаем почти в одно и тоже место и нужно шунтировать ветку чтобы уйти в другое направление.
Так вот, с длинным 268 байтным ключем, эти ветвления будут только первые 8 байт. Дальше мы выходим на плато и остальные 256+4 байт будут просканированы через обычный цикл for без каких либо джампов по памяти.

Теперь вы понимаете, что хештаблицы и всякие бинарные деревья, по своей задумке просто муссор по сравнению с структурами вроде HArray.

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

Твой код:

	bool getValueByKey(uint32* key,
		uint32 keyLen,
		uint32* value,
		uint32& valueLen)

опустим на время тот факт, что значене не всегда будет кратно 32-битам (или для чего ты uint32* используешь — поясни).

Допустим, я вставил значение длиной 900 байт (опять же, опустим на момент возмущение по поводу того почему именно 900 байт, а не любой размер как стандартные мапы позволяют)

Опустим тот факт, что value — это не тупой набор данных, который всегда можно тупо скопировать.

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

Копирование 900 байт из одного места памяти в другое займет дофига времени. И это только для того, чтоб получить доступ к значению. Мне может быть даже не нужны эти 900 байт, мне нужно только считать одно bool поле из моего значения, или передать ссылку куда-то вниз по стеку. Но даже для этого будут скопированы 900 байт.

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

На любом бенчмарке от твоей мапы ничего не останется.

Вдобавок, API, который ты запилил для функции — рецепт для выстрела себе в ногу.

	bool getValueByKey(uint32* key,
		uint32 keyLen,
		uint32* value,
		uint32& valueLen)

valueLen — это длина в байтах или в 32-битных словах? Я бы посмотрел ответ на свой вопрос в документации на этот метод, но, как ты сам знаешь, документацию на твою мапу не завезли.

Как твоя мапа знает, что память, которая выделена за *value достаточна, чтоб сохранить все значение? она ничего не проверяет, просто берет и фигачит в память. Если, например, я выделил 100 байт, а твоя мапа попытается записать 900 байт, то память будет похерена — добро пожаловать в неопределенное поведение и уязвимости типа buffer overflow, и это в 2021 году, когда даже в С++ уже завезли возможность писать почти без неопределенного поведения.

Нормальный API принимает на вход указатель на буфер и размер буфера. Внутри проверяют, чтоб не писать за пределы буфера, и, если места в буфере недостаточно, то возвращают ошибку типа ENOBUFS или бросают исключение.

— Кококо, ты не нашел больше до чего доебаться, решил доебаться до проверки на null!
Сорян, ты пишешь громкие слова про конкуренцию с стандартными универсальными структурами данных, причем сливаешь им и по скорости, и по дизайну и по каноничности и безопасности АПИ. Прийдется доебываться до всех трех.

опустим на время тот факт, что значене не всегда будет кратно 32-битам (или для чего ты uint32* используешь — поясни).

Есть враперы. Которые реализуют более конкретные интерфейсы.
Например такие
HArrayChar — Wrapper for HArray with interfaces: char* key, uint32 keyLen, char* value, uint32 valueLen
HArrayUniqueIntValueList — Wrapper for HArray with inteterfaces: uint32* key, uint32 keyLen, List listOfUniqueValues
Можешь написать свои. На любой вкус и цвет. У меня на один врапер уходило минут 15-20.

Копирование 900 байт из одного места памяти в другое займет дофига времени. И это только для того, чтоб получить доступ к значению. Мне может быть даже не нужны эти 900 байт, мне нужно только считать одно bool поле из моего значения, или передать ссылку куда-то вниз по стеку. Но даже для этого будут скопированы 900 байт.

Никто не будет копировать 900 байт, если ты сохранил например 4 или 8 байт. Будут копировать 4 или 8. Да даже если 900 байт ты сохранил, пулы никто не отменял чтобы просто вернуть ссылку на буфер. Запилить пул 50 строк кода, тебе надо ? Я могу прислать, у меня есть. Вообщем как обычно, сам придумал себе проблему, сам героически ее решаешь.

уязвимости типа buffer overflow

Если сделаешь через пул обьектов, оверфлоу не будет. Или можешь добавить эту проверку прямо в врапере, если для тебя это важно. Дело 2х минут.

Прийдется доебываться до всех трех.

Да можешь доеб*ться. Только делай это более профессионально со знанием дела.

Есть враперы. Которые реализуют более конкретные интерфейсы.

Теперь мне еще разбираться с ворохом недокументированных адаптеров к этому trie, потому что афтор не разобрался как сделать каноничный API как сделали на той же std::map?

Никто не будет копировать 900 байт, если ты сохранил например 4 или 8 байт. Будут копировать 4 или 8. Да даже если 900 байт ты сохранил, пулы никто не отменял чтобы просто вернуть ссылку на буфер. Запилить пул 50 строк кода, тебе надо ? Я могу прислать, у меня есть. Вообщем как обычно, сам придумал себе проблему, сам героически ее решаешь.

Это збс. Ты тут целый трактат написал про то как ты хитро придумал хранить большие значения в своей мапе. Но в итоге все свелось к тому же «храните 4 байтное значение, используйте пулы»
www.youtube.com/watch?v=U6Qrw6GdcxQ

Если сделаешь через пул обьектов, оверфлоу не будет. Или можешь добавить эту проверку прямо в врапере, если для тебя это важно. Дело 2х минут.

Скажи мне честно, стоило забивать на тему про швецию ради того, чтоб запилить кучу враперов, которые нельзя использовать по куче причин? Лучше б писал дальше про холодильники и колодец, было прикольнее.

Теперь мне еще разбираться с ворохом недокументированных адаптеров

Сколько можно ныть. Если бы я был таким нытиком как ты, который пасует перед мельчайшими проблемами, я бы такую супер мапу не написал бы даже за 150 лет.
Код врапера, 50 строк кода, который просто перекидует одни интерфейсы на другие.
Что тут сложного ?

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

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

которые нельзя использовать по куче причин

Нельзя использовать только у таких специалистов как ты. Которые рисуют себе тысячу вымышленных проблем.

Код врапера, 50 строк кода, который просто перекидует одни интерфейсы на другие.
Что тут сложного ?

Если мне захочется копипастить boilerplate code, я пойду на Go. На С++ такой херней никто не занимается, люди ожидают универсальную структуру с темплейтами, работающую из коробки.

Это особенности реализации. Я не храню ключ и велью как непрерывный набор байт под капотом. Более того, эти самые байты могут быть сжаты префиксной компрессией. Я даже не знаю какой нужно уровень иметь, чтобы не понимать такие вещи и требовать невозможного.

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

ограничениях твоей реализации

Пока я не увидел непреодолимых ограничений.

И задайся вопросом, почему я, чувак, который не осилил С++ и даже уволился с работы, чтоб не иметь дела с С++, должен тебе все это объяснять. Где остальные плюсовики, которые должны все эти косяки спинным мозгом чувствовать и бить тревогу? То ли их нет, то ли они десятой дорогой обходят твой топик.

Потому что нормальные плюсовики пишут в Си стиле, как я. И не морочат себе голову. И эти темплейты по большому счету нахер никому не надо в том виде в котором они есть. Конечно приятно поставить галочку что мапа теперь полностью соответствует интерфейсам std map Но с практической точки зрения в реальном проекте мою мапу использовать даже проще. Не говоря о том что она в 10 раз быстрее работает и более щадящая по памяти.

нормальные плюсовики пишут в Си стиле, как я

Так собі заявка на елітарність. Не можу в С++ — значить правильний С++ обмежується тим, що я можу.

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

Як бути з тим, що ці «нікому не потрібні темплейти» у вигляді елементарних vector чи shared_ptr є будь-якому С++ коді складнішому за «Hello world»?

Нормальный API принимает на вход указатель на буфер и размер буфера.

Ну это ж оно и есть?

uint32* value,
uint32& valueLen)

тут уже я что-то совсем не понимаю, что тебе не нравится...

Внутри проверяют, чтоб не писать за пределы буфера, и, если места в буфере недостаточно, то возвращают ошибку типа ENOBUFS или бросают исключение.

И это обычный вариант: в valueLen пишут реальную длину значения, а если она больше переданного на входе — произошло усечение.

Да, значение в виде массива uint32 это странно, он должен сам делать паддинг, по идее. В остальном-то что не так?

Нормальный API принимает на вход указатель на буфер и размер буфера.
Ну это ж оно и есть?

uint32* value,
uint32& valueLen)
тут уже я что-то совсем не понимаю, что тебе не нравится...

github.com/...​HArrayLongValue.h#L80-L95

valueLen используется только для вывода кол-ва прочитанных байт (слов?) из функции. Размер входного буфера нигде не указан и не проверяется, походу ожидается, что можно писать пока память не закончится.

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

Ааааааааа! Это точно диверсия :((

не надо так. В map нет никаких значений произвольной длины, все значения занимают sizeof(v) байтиков. Посмотри уже наконец, как работает мапа, там несложно

Эээ ...
Это что получается, я могу создать мап только с фиксированой длиной ключа sizeof(k) и фиксированой длиной велью sizeof(v) ? Тоесть я не могу вставлять в один и тотже инстанц мапы ключи разной длины ?

Печаль. Одни из первых версий которые я делал, работали именно с ключами фиксированой длины и работали в два раза быстрее чем текущая версия. Ради фичи вставлять ключи разной длины в один и тотже контейнер (которая полезна в реальных проекта) пришлось свой код замедлить даже больше чем в 2 раза. Я точно помню, даже на слабее машинке 10 млн 16ти байтных рандом ключей вставлял и читал меньше чем за 1 секунду, а сейчас больше 2х секунд. Это конечно все еще в несколько раз быстрее чем std::map, но осадочек остался. Может быть стоит форкнуть версию и сделать версию именно с ключами фиксированой длины в контейнере.

Это что получается, я могу создать мап только с фиксированой длиной ключа sizeof(k) и фиксированой длиной велью sizeof(v) ?
fn main() {
    let mut map1 = BTreeMap::new();

    map1.insert(vec![0, 5, 7, 8], "first");
    map1.insert(vec![42], "second");

    let mut map2 = HashMap::new();
    map2.insert(map1, 123456);
}

Так std::map вроде тоже подобный код поддерживает.
Только потом выясняется что он ссылки на эти обьекты хранит (которые фиксированой длины), а не делает честную побайтовую копию обьектов прозвольной длины и помещает внутрь контейнера.

map1.insert(vec![0, 5, 7, 8], "first");
map1.insert(vec![42], "second");

Но я считаю что у меня это скорей киллер фича. Для СУБД мапа которая хранит ссылки на обьекты в качестве ключей, по сути бесполезна и не может выступать в качестве основного storage механизма. Потому что нормальный storage должен делать копию обьекта произвольной длины и его хранить независимо от внешнего кода.

В коде, который я привел, ключ вставляется в мапу(а не ссылка), мапа владеет ключем, а не содержит ссылку на него. Синтаксис для передачи ссылки отличается.

Вставка ключа внутрь мапы:

    let key = vec![0, 5, 7, 8];
    map1.insert(key, "first");

Вставка ссылки на ключ внутрь мапы:

    let key = vec![0, 5, 7, 8];
    map1.insert(&key, "first");

Ок, значит в Расте мапа работает так как у меня.
Да и в других языках, вроде .NET и Java, такое же поведение.
Поэтому меня и удивило, почему std::map работает иначе, с урезаным функционалом.

Поэтому меня и удивило, почему std::map работает иначе, с урезаным функционалом.

дайте мне пистолет с одним патроном

Ок, значит в Расте мапа работает так как у меня.

В таком случае я должен спросить, какой был смысл писать свою мапу, если можно было использовать растовскую?

Может из-за этого ?

1. Очень высокая скорость работы. Тестирование без всяких подвохов, Key/Value контейнер имеет достаточно простые сценарии использования. В среднем HArray в 5-10 раз быстрее работает чем типичные реализации контейнеров вроде std::map, при этом имея даже немного более широкую функциональность. И в многих кейсах работает быстрее чем Hashtables, особенно на скорости вставок. Единственный кейс где Hashtables уверенно обгоняет HArray, это ключи последовательной природы, вроде 1,2,3 и тд. Но ирония в том, что для таких ключей Вам не нужен HArray, не нужен Hashtables или другой map, а подойдет обычный массив.

2. Малое потребление памяти. Для монотонных ключей, которые имеют общий префикс (пути к файлам, пути к обьектам, словари и тд) возможна компрессия данных по сравнению с оригинальным их размером. Компрессия данных невозможна в бинарных деревьях и тем более в хештаблицах, где перерасход памяти стабильно составляет в 2-3 раза.

3. Данные в контейнере находятся в сортированом (или близком к этому) виде. Возможность очень быстро определять, есть ли ключ с каким либо префиксом в контейнере. Доступна широкая функциональность по скану ключей. Возможность сканировать поддиапазоны ключей. При этом при сканировании поддиапазона мы не читаем все ключи вподряд, а как бы сканируем только «хвосты» ключей. Такая функциональность недоступна в хештаблицах и доступна в неоптимальном виде в бинарных деревьях.

4. Специфические, но не синтетические, контр примеры. Это когда вставляются длинные ключи с похожими префиксами. Они не использовались в бенчмарках, чтобы не давать HArray явное преимущество, но на этих контр примерах потребление памяти и скорость работы может отличатся в десятки и сотни раз в пользу HArray.

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

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

7. Удаление ключей с плавным освобождением памяти и упрощения структуры.

Потому что нормальный storage должен делать копию обьекта произвольной длины и его хранить независимо от внешнего кода.

Ты можешь сделать LSM tree и хранить всё в больших блобах. Вполне рабочий путь даже в оперативной памяти.

я могу создать мап только с фиксированой длиной ключа sizeof(k) и фиксированой длиной велью sizeof(v)

std::map типізована, тобто знає тип ключа і тип значення. І відповідно вміє їх правильно конструювати, копіювати, переміщувати і знищувати.

відповідно вміє їх правильно конструювати, копіювати, переміщувати і знищувати.

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

Это артефакт алгоритма конкретно этой мапы

Это артефакт C++.

как и необходимость имплементить хешфункцию

Для std::map? Держи контекст крепче.

HArray не нужны хешфункции, он никогда не перемещает ключи в памяти целиком.

Я тому і сказав, що це скоріше структура як більше для С підходить, ніж для С++. Ти даєш аналог чогось типу int harray[size] (що, до речі працює швидше ніж твоя реалізація), а на питання про те як вирахувати індекс відповідаєш «напиши простенький пул». В той час як контейнери STL підтримують будь-які типи, правильно роблять копіювання та переміщення, контролюють час життя об’єктів, можуть використовуватися навіть коли інформація про конкретний тип контейнера втрачена (наприклад з ітераторами чи алгоритмами).

правильно роблять копіювання та переміщення

Я так и не понял зачем чтото копировать или перемещать в мапе.
std::map балансирует страницы в красно-черном дереве, перемещает элементы с слота в слот, ну отлично. Это особенности имплементации этой мапы. Мне ничего копировать и перемещать не надо. Я не требую этого от клиентского кода.

не понял зачем чтото копировать или перемещать в мапе

А ось такий приклад:

map<string, string> m1;
string s1 = "key1";
m1[s1] = "value1"; // ключ копіюємо
s1 = "value2";
m1["key2"] = s1; // значення копіюємо

Переміщення знадобиться коли передаємо контроль, робимо swap, реалокуємо буфер і так далі. Потрібно для того щоб не створювати тимчасові копії.

Так я ровно также копирую. Этот пример валиден с харреем. Мне передали буфер я его скопировал в внутренние структуры. Я не храню ссылки на объект.
А вот у std:map проблемы если тип это банальный char*.

Мне передали буфер

В std::map не буфер, а значення типу. А відповідно такі значення правильно конструюються, копіюються та знищуються. Можуть всередині містити вказівники та посилання на інші об’єкти будь-якої глибини.

Как std::map работает с типом char*
Ответ — никак. Он будет хранить 4 байта, адресс в пам’яти а не массив байт.
Это отвечает на вопрос харрей вс стд мап. Сохранить там ключ как набор байт это ещё та головная боль в отличии от.

Як і з будь-яким вказівником на будь-який тип — як з об’єктами типу T* — тобто як з цілочисельними значеннями. Тому запихати вказівники на об’єкти в контейнери вкрай не варто. Для того щоб char* працював у мапі нормально доведеться свій компаратор писати, по мінімуму щось типу:

map m;

Сорі, в коменті вище було трошки коду, але парсер усе порізав. Мало б бути щось таке:

map m<char*, int, strcmp>;

В прикладі вище звісно не «ключ копіюємо», а «значення конструюємо».

Тьфу ты, я думал тут про мотоцикл

Как его запустить? при make у меня куча error вылетает

Пишет что ты криворукий ))))))))

Тебя мама не кормит ? Почему такой злой.

Target: x86_64-linux-gnu
Configured with: ../src/configure -v —with-pkgversion=’Ubuntu 10.3.0-1ubuntu1′ —with-bugurl=file:///usr/share/doc/gcc-10/README.Bugs —enable-languages=c,ada,c++,go,brig,d,fortran,objc,obj-c++,m2 —prefix=/usr —with-gcc-major-version-only —program-suffix=-10 —program-prefix=x86_64-linux-gnu- —enable-shared —enable-linker-build-id —libexecdir=/usr/lib —without-included-gettext —enable-threads=posix —libdir=/usr/lib —enable-nls —enable-bootstrap —enable-clocale=gnu —enable-libstdcxx-debug —enable-libstdcxx-time=yes —with-default-libstdcxx-abi=new —enable-gnu-unique-object —disable-vtable-verify —enable-plugin —enable-default-pie —with-system-zlib —enable-libphobos-checking=release —with-target-system-zlib=auto —enable-objc-gc=auto —enable-multiarch —disable-werror —with-arch-32=i686 —with-abi=m64 —with-multilib-list=m32,m64,mx32 —enable-multilib —with-tune=generic —enable-offload-targets=nvptx-none=/build/gcc-10-gDeRY6/gcc-10-10.3.0/debian/tmp-nvptx/usr,amdgcn-amdhsa=/build/gcc-10-gDeRY6/gcc-10-10.3.0/debian/tmp-gcn/usr,hsa —without-cuda-driver —enable-checking=release —build=x86_64-linux-gnu —host=x86_64-linux-gnu —target=x86_64-linux-gnu —with-build-config=bootstrap-lto-lean —enable-link-mutex
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 10.3.0 (Ubuntu 10.3.0-1ubuntu1)

Main.cpp:854:6: error: variable or field ‘testHArrayStr’ declared void
854 | void testHArrayStr(std::string* keys, uint32 countKeys)
| ^~~~~~~~~~~~~
Main.cpp:854:25: error: ‘string’ is not a member of ‘std’
854 | void testHArrayStr(std::string* keys, uint32 countKeys)
| ^~~~~~
Main.cpp:28:1: note: ‘std::string’ is defined in header ‘’; did you forget to ‘#include ’?
27 | #include “HArray.h”
+++ |+#include
28 |
Main.cpp:854:33: error: ‘keys’ was not declared in this scope
854 | void testHArrayStr(std::string* keys, uint32 countKeys)
| ^~~~
Main.cpp:854:46: error: expected primary-expression before ‘countKeys’
854 | void testHArrayStr(std::string* keys, uint32 countKeys)
| ^~~~~~~~~
Main.cpp:992:6: error: variable or field ‘testHArrayStrVar’ declared void
992 | void testHArrayStrVar(std::string* keys, uint32 countKeys)
| ^~~~~~~~~~~~~~~~
Main.cpp:992:28: error: ‘string’ is not a member of ‘std’
992 | void testHArrayStrVar(std::string* keys, uint32 countKeys)
| ^~~~~~
Main.cpp:992:28: note: ‘std::string’ is defined in header ‘’; did you forget to ‘#include ’?
Main.cpp:992:36: error: ‘keys’ was not declared in this scope
992 | void testHArrayStrVar(std::string* keys, uint32 countKeys)
| ^~~~
Main.cpp:992:49: error: expected primary-expression before ‘countKeys’
992 | void testHArrayStrVar(std::string* keys, uint32 countKeys)
| ^~~~~~~~~
Main.cpp:1180:6: error: variable or field ‘testStdMapStr’ declared void
1180 | void testStdMapStr(std::string* keys, uint32 countKeys)
| ^~~~~~~~~~~~~
Main.cpp:1180:25: error: ‘string’ is not a member of ‘std’
1180 | void testStdMapStr(std::string* keys, uint32 countKeys)
| ^~~~~~
Main.cpp:1180:25: note: ‘std::string’ is defined in header ‘’; did you forget to ‘#include ’?
Main.cpp:1180:33: error: ‘keys’ was not declared in this scope
1180 | void testStdMapStr(std::string* keys, uint32 countKeys)
| ^~~~
Main.cpp:1180:46: error: expected primary-expression before ‘countKeys’
1180 | void testStdMapStr(std::string* keys, uint32 countKeys)
| ^~~~~~~~~
Main.cpp:1230:6: error: variable or field ‘testDenseHashMapStr’ declared void
1230 | void testDenseHashMapStr(std::string* keys, uint32 countKeys)
| ^~~~~~~~~~~~~~~~~~~
Main.cpp:1230:31: error: ‘string’ is not a member of ‘std’
1230 | void testDenseHashMapStr(std::string* keys, uint32 countKeys)
| ^~~~~~
Main.cpp:1230:31: note: ‘std::string’ is defined in header ‘’; did you forget to ‘#include ’?
Main.cpp:1230:39: error: ‘keys’ was not declared in this scope
1230 | void testDenseHashMapStr(std::string* keys, uint32 countKeys)
| ^~~~
Main.cpp:1230:52: error: expected primary-expression before ‘countKeys’
1230 | void testDenseHashMapStr(std::string* keys, uint32 countKeys)
| ^~~~~~~~~
Main.cpp:1283:6: error: variable or field ‘testStdUnorderedMapStr’ declared void
1283 | void testStdUnorderedMapStr(std::string* keys, uint32 countKeys)
| ^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:1283:34: error: ‘string’ is not a member of ‘std’
1283 | void testStdUnorderedMapStr(std::string* keys, uint32 countKeys)
| ^~~~~~
Main.cpp:1283:34: note: ‘std::string’ is defined in header ‘’; did you forget to ‘#include ’?
Main.cpp:1283:42: error: ‘keys’ was not declared in this scope
1283 | void testStdUnorderedMapStr(std::string* keys, uint32 countKeys)
| ^~~~
Main.cpp:1283:55: error: expected primary-expression before ‘countKeys’
1283 | void testStdUnorderedMapStr(std::string* keys, uint32 countKeys)
| ^~~~~~~~~
Main.cpp:1335:6: error: variable or field ‘fillSeqStrs’ declared void
1335 | void fillSeqStrs(std::string* keys, uint32 countKeys)
| ^~~~~~~~~~~
Main.cpp:1335:23: error: ‘string’ is not a member of ‘std’
1335 | void fillSeqStrs(std::string* keys, uint32 countKeys)
| ^~~~~~
Main.cpp:1335:23: note: ‘std::string’ is defined in header ‘’; did you forget to ‘#include ’?
Main.cpp:1335:31: error: ‘keys’ was not declared in this scope
1335 | void

fillSeqStrs(std::string* keys, uint32 countKeys)
| ^~~~
Main.cpp:1335:44: error: expected primary-expression before ‘countKeys’
1335 | void fillSeqStrs(std::string* keys, uint32 countKeys)
| ^~~~~~~~~
Main.cpp:1352:6: error: variable or field ‘fillRandStrs’ declared void
1352 | void fillRandStrs(std::string* keys, uint32 countKeys)
| ^~~~~~~~~~~~
Main.cpp:1352:24: error: ‘string’ is not a member of ‘std’
1352 | void fillRandStrs(std::string* keys, uint32 countKeys)
| ^~~~~~
Main.cpp:1352:24: note: ‘std::string’ is defined in header ‘’; did you forget to ‘#include ’?
Main.cpp:1352:32: error: ‘keys’ was not declared in this scope
1352 | void fillRandStrs(std::string* keys, uint32 countKeys)
| ^~~~
Main.cpp:1352:45: error: expected primary-expression before ‘countKeys’
1352 | void fillRandStrs(std::string* keys, uint32 countKeys)
| ^~~~~~~~~
Main.cpp: In function ‘void HArray_VS_StdMap_StrKey(uint32, uint32, uint32)’:
Main.cpp:1370:7: error: ‘string’ is not a member of ‘std’
1370 | std::string* strKeys = new std::string[stopOnAmount];
| ^~~~~~
Main.cpp:1370:7: note: ‘std::string’ is defined in header ‘’; did you forget to ‘#include ’?
Main.cpp:1370:15: error: ‘strKeys’ was not declared in this scope
1370 | std::string* strKeys = new std::string[stopOnAmount];
| ^~~~~~~
Main.cpp:1370:34: error: ‘string’ in namespace ‘std’ does not name a type
1370 | std::string* strKeys = new std::string[stopOnAmount];
| ^~~~~~
Main.cpp:1370:29: note: ‘std::string’ is defined in header ‘’; did you forget to ‘#include ’?
1370 | std::string* strKeys = new std::string[stopOnAmount];
| ^~~
Main.cpp:1374:2: error: ‘fillSeqStrs’ was not declared in this scope; did you mean ‘fillSeqBins’?
1374 | fillSeqStrs(strKeys, stopOnAmount);
| ^~~~~~~~~~~
| fillSeqBins
Main.cpp:1379:3: error: ‘testHArrayStr’ was not declared in this scope; did you mean ‘testHArrayBin’?
1379 | testHArrayStr(strKeys, countKeys);
| ^~~~~~~~~~~~~
| testHArrayBin
Main.cpp:1380:3: error: ‘testDenseHashMapStr’ was not declared in this scope; did you mean ‘testDenseHashMapBin’?
1380 | testDenseHashMapStr(strKeys, countKeys);
| ^~~~~~~~~~~~~~~~~~~
| testDenseHashMapBin
Main.cpp:1381:3: error: ‘testStdMapStr’ was not declared in this scope; did you mean ‘testStdMapBin’?
1381 | testStdMapStr(strKeys, countKeys);
| ^~~~~~~~~~~~~
| testStdMapBin
Main.cpp:1382:3: error: ‘testStdUnorderedMapStr’ was not declared in this scope; did you mean ‘testStdUnorderedMapBin’?
1382 | testStdUnorderedMapStr(strKeys, countKeys);
| ^~~~~~~~~~~~~~~~~~~~~~
| testStdUnorderedMapBin
Main.cpp:1390:2: error: ‘fillRandStrs’ was not declared in this scope; did you mean ‘fillRandBins’?
1390 | fillRandStrs(strKeys, stopOnAmount);
| ^~~~~~~~~~~~
| fillRandBins
Main.cpp:1395:3: error: ‘testHArrayStr’ was not declared in this scope; did you mean ‘testHArrayBin’?
1395 | testHArrayStr(strKeys, countKeys);
| ^~~~~~~~~~~~~
| testHArrayBin
Main.cpp:1396:3: error: ‘testDenseHashMapStr’ was not declared in this scope; did you mean ‘testDenseHashMapBin’?
1396 | testDenseHashMapStr(strKeys, countKeys);
| ^~~~~~~~~~~~~~~~~~~
| testDenseHashMapBin
Main.cpp:1397:3: error: ‘testStdMapStr’ was not declared in this scope; did you mean ‘testStdMapBin’?
1397 | testStdMapStr(strKeys, countKeys);
| ^~~~~~~~~~~~~
| testStdMapBin
Main.cpp:1398:3: error: ‘testStdUnorderedMapStr’ was not declared in this scope; did you mean ‘testStdUnorderedMapBin’?
1398 | testStdUnorderedMapStr(strKeys, countKeys);
| ^~~~~~~~~~~~~~~~~~~~~~
| testStdUnorderedMapBin
Main.cpp:1404:11: error: type ‘’ argument given to ‘delete’, expected pointer
1404 | delete[] strKeys;
| ^~~~~~~
Main.cpp: In function ‘void HArray_VS_StdMap_StrKey_Var(uint32, uint32, uint32)’:
Main.cpp:1415:7: error: ‘string’ is not a member of ‘std’
1415 | std::string* strKeys = new std::string[stopOnAmount];
| ^~~~~~
Main.cpp:1415:7: note: ‘std::string’ is defined in header ‘’; did you forget to

‘#include ’?
Main.cpp:1415:15: error: ‘strKeys’ was not declared in this scope
1415 | std::string* strKeys = new std::string[stopOnAmount];
| ^~~~~~~
Main.cpp:1415:34: error: ‘string’ in namespace ‘std’ does not name a type
1415 | std::string* strKeys = new std::string[stopOnAmount];
| ^~~~~~
Main.cpp:1415:29: note: ‘std::string’ is defined in header ‘’; did you forget to ‘#include ’?
1415 | std::string* strKeys = new std::string[stopOnAmount];
| ^~~
Main.cpp:1419:2: error: ‘fillRandStrs’ was not declared in this scope; did you mean ‘fillRandBins’?
1419 | fillRandStrs(strKeys, stopOnAmount);
| ^~~~~~~~~~~~
| fillRandBins
Main.cpp:1424:3: error: ‘testHArrayStrVar’ was not declared in this scope; did you mean ‘testHArrayBin’?
1424 | testHArrayStrVar(strKeys, countKeys);
| ^~~~~~~~~~~~~~~~
| testHArrayBin
Main.cpp:1430:11: error: type ‘’ argument given to ‘delete’, expected pointer
1430 | delete[] strKeys;
| ^~~~~~~

Говорил, что код на марсоход можно ставить, а он даже не собирается.

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

Говорил, что код на марсоход можно ставить, а он даже не собирается.

Ну ошибки нужно читать.
Его компилятор почему-то не видит std::string.
Я добавил явно
#include string в main.
Но вообще-то, в stdafx.h уже есть подобная строчка. И везде такой код компилировался.
Так что хз или поможет. Вполне могут быть проблемы с этой специфической машиной и настройками компилятора на ней.

У меня Убунту обычная и компилятор из коробки.

Его компилятор почему-то не видит std::string.
Я добавил явно
#include string в main.
Но вообще-то, в stdafx.h уже есть подобная строчка. И везде такой код компилировался.
Так что хз или поможет. Вполне могут быть проблемы с этой специфической машиной и настройками компилятора на ней.

т.е. ты фиксишь код и делаешь комиты, даже не понимая в чем ошибка и не воспроизведя ее, и не знашеь, твой фикс исправит ошибку или нет? Збс, как раз уровень качества для марсохода.

т.е. ты фиксишь код и делаешь комиты, даже не понимая в чем ошибка и не воспроизведя ее, и не знашеь, твой фикс исправит ошибку или нет? Збс, как раз уровень качества для марсохода.

Код я разрабатываю и компилирую в Visual Studio. Потому что удобнее VS ничего не придумали. И уже только потом проверяю под другие компиляторы на Линукс машине. В данном случае код полностью компилировался и работал под Visual Studio на винде, но перестал собираться под Линукс. Что я уже пофиксил.

Код я разрабатываю и компилирую в Visual Studio. Потому что удобнее VS ничего не придумали.

CLion
Code Blocks
Visual Studio Code
Vim

Ты просто VS не видел. Как раз пол часа назад дебажил в Code::Blocks по сравнению с VS он выглядит как текстовый редактор.

Тебе вообще-то первым пунктом CLion назвали.

Ошибки со стрингами пропали, но сейчас вот эти:

g++ HArray_delValueByKey.cpp HArray_getValueByKey.cpp HArray_getKeysAndValuesByRange.cpp HArray_hasPartKey.cpp HArray_insert.cpp HArray_scanKeysAndValues.cpp HArray_rebuild.cpp HArray_resizeHeader.cpp HArray_shrink.cpp HArray_test.cpp Main.cpp -o HArray -w
In file included from HArray_delValueByKey.cpp:20:
HArray.h: In member function ‘bool HArray::saveToFile(const char*)’:
HArray.h:213:3: error: ‘errno_t’ was not declared in this scope
213 | errno_t errorCode = fopen_s(&pFile, path, „wb”);
| ^~~~~~~
HArray.h:215:10: error: ‘errorCode’ was not declared in this scope
215 | if (!errorCode)
| ^~~~~~~~~
HArray.h: In member function ‘bool HArray::loadFromFile(const char*)’:
HArray.h:300:3: error: ‘errno_t’ was not declared in this scope
300 | errno_t errorCode = fopen_s(&pFile, path, „rb”);
| ^~~~~~~
HArray.h:302:10: error: ‘errorCode’ was not declared in this scope
302 | if (!errorCode)
| ^~~~~~~~~
In file included from HArray_getValueByKey.cpp:20:
HArray.h: In member function ‘bool HArray::saveToFile(const char*)’:
HArray.h:213:3: error: ‘errno_t’ was not declared in this scope
213 | errno_t errorCode = fopen_s(&pFile, path, „wb”);
| ^~~~~~~
HArray.h:215:10: error: ‘errorCode’ was not declared in this scope
215 | if (!errorCode)
| ^~~~~~~~~
HArray.h: In member function ‘bool HArray::loadFromFile(const char*)’:
HArray.h:300:3: error: ‘errno_t’ was not declared in this scope
300 | errno_t errorCode = fopen_s(&pFile, path, „rb”);
| ^~~~~~~
HArray.h:302:10: error: ‘errorCode’ was not declared in this scope
302 | if (!errorCode)
| ^~~~~~~~~
In file included from HArray_getKeysAndValuesByRange.cpp:20:
HArray.h: In member function ‘bool HArray::saveToFile(const char*)’:
HArray.h:213:3: error: ‘errno_t’ was not declared in this scope
213 | errno_t errorCode = fopen_s(&pFile, path, „wb”);
| ^~~~~~~
HArray.h:215:10: error: ‘errorCode’ was not declared in this scope
215 | if (!errorCode)
| ^~~~~~~~~
HArray.h: In member function ‘bool HArray::loadFromFile(const char*)’:
HArray.h:300:3: error: ‘errno_t’ was not declared in this scope
300 | errno_t errorCode = fopen_s(&pFile, path, „rb”);
| ^~~~~~~
HArray.h:302:10: error: ‘errorCode’ was not declared in this scope
302 | if (!errorCode)
| ^~~~~~~~~
In file included from HArray_hasPartKey.cpp:20:
HArray.h: In member function ‘bool HArray::saveToFile(const char*)’:
HArray.h:213:3: error: ‘errno_t’ was not declared in this scope
213 | errno_t errorCode = fopen_s(&pFile, path, „wb”);
| ^~~~~~~
HArray.h:215:10: error: ‘errorCode’ was not declared in this scope
215 | if (!errorCode)
| ^~~~~~~~~
HArray.h: In member function ‘bool HArray::loadFromFile(const char*)’:
HArray.h:300:3: error: ‘errno_t’ was not declared in this scope
300 | errno_t errorCode = fopen_s(&pFile, path, „rb”);
| ^~~~~~~
HArray.h:302:10: error: ‘errorCode’ was not declared in this scope
302 | if (!errorCode)
| ^~~~~~~~~
In file included from HArray_insert.cpp:21:
HArray.h: In member function ‘bool HArray::saveToFile(const char*)’:
HArray.h:213:3: error: ‘errno_t’ was not declared in this scope
213 | errno_t errorCode = fopen_s(&pFile, path, „wb”);
| ^~~~~~~
HArray.h:215:10: error: ‘errorCode’ was not declared in this scope
215 | if (!errorCode)
| ^~~~~~~~~
HArray.h: In member function ‘bool HArray::loadFromFile(const char*)’:
HArray.h:300:3: error: ‘errno_t’ was not declared in this scope
300 | errno_t errorCode = fopen_s(&pFile, path, „rb”);
| ^~~~~~~
HArray.h:302:10: error: ‘errorCode’ was not declared in this scope
302 | if (!errorCode)
| ^~~~~~~~~
HArray_insert.cpp: In member function ‘bool HArray::insert(uint32*, uint32, uint32)’:
HArray_insert.cpp:1489:2: error: jump to label ‘FILL_KEY’
1489 | FILL_KEY:
| ^~~~~~~~
HArray_insert.cpp:488:12: note: from here
488 | goto FILL_KEY;
| ^~~~~~~~
HArray_insert.cpp:552:10: note: crosses initialization of ‘uint32 keyValue’
552 | uint32 keyValue = key[keyOffset];
| ^~~~~~~~
HArray_insert.cpp:1489:2: error: jump to label ‘FILL_KEY’
1489 | FILL_KEY:
| ^~~~~~~~
HArray_insert.cpp:313:12: note: from here
313 | goto FILL_KEY;
|

^~~~~~~~
HArray_insert.cpp:552:10: note: crosses initialization of ‘uint32 keyValue’
552 | uint32 keyValue = key[keyOffset];
| ^~~~~~~~
HArray_insert.cpp:1493:2: error: jump to label ‘FILL_KEY2’
1493 | FILL_KEY2:
| ^~~~~~~~~
HArray_insert.cpp:539:11: note: from here
539 | goto FILL_KEY2;
| ^~~~~~~~~
HArray_insert.cpp:552:10: note: crosses initialization of ‘uint32 keyValue’
552 | uint32 keyValue = key[keyOffset];
| ^~~~~~~~
HArray_insert.cpp:1493:2: error: jump to label ‘FILL_KEY2’
1493 | FILL_KEY2:
| ^~~~~~~~~
HArray_insert.cpp:361:11: note: from here
361 | goto FILL_KEY2;
| ^~~~~~~~~
HArray_insert.cpp:552:10: note: crosses initialization of ‘uint32 keyValue’
552 | uint32 keyValue = key[keyOffset];
| ^~~~~~~~
In file included from HArray_scanKeysAndValues.cpp:20:
HArray.h: In member function ‘bool HArray::saveToFile(const char*)’:
HArray.h:213:3: error: ‘errno_t’ was not declared in this scope
213 | errno_t errorCode = fopen_s(&pFile, path, „wb”);
| ^~~~~~~
HArray.h:215:10: error: ‘errorCode’ was not declared in this scope
215 | if (!errorCode)
| ^~~~~~~~~
HArray.h: In member function ‘bool HArray::loadFromFile(const char*)’:
HArray.h:300:3: error: ‘errno_t’ was not declared in this scope
300 | errno_t errorCode = fopen_s(&pFile, path, „rb”);
| ^~~~~~~
HArray.h:302:10: error: ‘errorCode’ was not declared in this scope
302 | if (!errorCode)
| ^~~~~~~~~
In file included from HArray_rebuild.cpp:20:
HArray.h: In member function ‘bool HArray::saveToFile(const char*)’:
HArray.h:213:3: error: ‘errno_t’ was not declared in this scope
213 | errno_t errorCode = fopen_s(&pFile, path, „wb”);
| ^~~~~~~
HArray.h:215:10: error: ‘errorCode’ was not declared in this scope
215 | if (!errorCode)
| ^~~~~~~~~
HArray.h: In member function ‘bool HArray::loadFromFile(const char*)’:
HArray.h:300:3: error: ‘errno_t’ was not declared in this scope
300 | errno_t errorCode = fopen_s(&pFile, path, „rb”);
| ^~~~~~~
HArray.h:302:10: error: ‘errorCode’ was not declared in this scope
302 | if (!errorCode)
| ^~~~~~~~~
In file included from HArray_resizeHeader.cpp:21:
HArray.h: In member function ‘bool HArray::saveToFile(const char*)’:
HArray.h:213:3: error: ‘errno_t’ was not declared in this scope
213 | errno_t errorCode = fopen_s(&pFile, path, „wb”);
| ^~~~~~~
HArray.h:215:10: error: ‘errorCode’ was not declared in this scope
215 | if (!errorCode)
| ^~~~~~~~~
HArray.h: In member function ‘bool HArray::loadFromFile(const char*)’:
HArray.h:300:3: error: ‘errno_t’ was not declared in this scope
300 | errno_t errorCode = fopen_s(&pFile, path, „rb”);
| ^~~~~~~
HArray.h:302:10: error: ‘errorCode’ was not declared in this scope
302 | if (!errorCode)
| ^~~~~~~~~
HArray_resizeHeader.cpp: At global scope:
HArray_resizeHeader.cpp:23:6: error: no declaration matches ‘void HArray::resizeHeader()’
23 | void HArray::resizeHeader()
| ^~~~~~
HArray_resizeHeader.cpp:23:6: note: no functions named ‘void HArray::resizeHeader()’
In file included from HArray_resizeHeader.cpp:21:
HArray.h:28:7: note: ‘class HArray’ defined here
28 | class HArray
| ^~~~~~
In file included from HArray_shrink.cpp:21:
HArray.h: In member function ‘bool HArray::saveToFile(const char*)’:
HArray.h:213:3: error: ‘errno_t’ was not declared in this scope
213 | errno_t errorCode = fopen_s(&pFile, path, „wb”);
| ^~~~~~~
HArray.h:215:10: error: ‘errorCode’ was not declared in this scope
215 | if (!errorCode)
| ^~~~~~~~~
HArray.h: In member function ‘bool HArray::loadFromFile(const char*)’:
HArray.h:300:3: error: ‘errno_t’ was not declared in this scope
300 | errno_t errorCode = fopen_s(&pFile, path, „rb”);
| ^~~~~~~
HArray.h:302:10: error: ‘errorCode’ was not declared in this scope
302 | if (!errorCode)
| ^~~~~~~~~
In file included from HArray_test.cpp:21:
HArray.h: In member function ‘bool HArray::saveToFile(const char*)’:
HArray.h:213:3: error: ‘errno_t’ was not declared in this scope
213 | errno_t errorCode = fopen_s(&pFile, path, „wb”);
| ^~~~~~~
HArray.h:215:10: error: ‘errorCode’ was not declared in this scope
215 | if (!errorCode)
|

^~~~~~~~~
HArray.h: In member function ‘bool HArray::loadFromFile(const char*)’:
HArray.h:300:3: error: ‘errno_t’ was not declared in this scope
300 | errno_t errorCode = fopen_s(&pFile, path, „rb”);
| ^~~~~~~
HArray.h:302:10: error: ‘errorCode’ was not declared in this scope
302 | if (!errorCode)
| ^~~~~~~~~
In file included from Main.cpp:28:
HArray.h: In member function ‘bool HArray::saveToFile(const char*)’:
HArray.h:213:3: error: ‘errno_t’ was not declared in this scope; did you mean ‘error_t’?
213 | errno_t errorCode = fopen_s(&pFile, path, „wb”);
| ^~~~~~~
| error_t
HArray.h:215:10: error: ‘errorCode’ was not declared in this scope
215 | if (!errorCode)
| ^~~~~~~~~
HArray.h: In member function ‘bool HArray::loadFromFile(const char*)’:
HArray.h:300:3: error: ‘errno_t’ was not declared in this scope; did you mean ‘error_t’?
300 | errno_t errorCode = fopen_s(&pFile, path, „rb”);
| ^~~~~~~
| error_t
HArray.h:302:10: error: ‘errorCode’ was not declared in this scope
302 | if (!errorCode)
| ^~~~~~~~~
make: *** [makefile:2: all] Error 1

Вот так сиди, убирай ворнинги.
Visual Studio ругалась ворнингом, что замените fopen на fopen_s
При этом получается fopen_s с ее структурой errno_t под линукс уже не компилится,
потому что fopen_s ниразу не стандарт.
Получается нужна развилка отдельно под линукс, отдельно под виндовз.
От фикса ворнингов похоже больше вреда чем пользы получилось.

Ладно, доберусь до убунту машины, перепроверю. Чтоб не дергать если еще что всплывет.
Спасибо за труд, хорошо что обнаружилось.

Из доки

Serialize/Deserialize from/to file at a speed close to the max speed of hard drive

HArray ha;

ha.saveToFile("c:\\dump");

ha.loadFromFile("c:\\dump");

Ок. И при чём тут хэш к сериализатору/десериализатору?

Одна из фишек HArray, что при сохранении на диск, он не обходит весь граф обьектов, что может быть очень долго. Он просто сбрасывает страницы памяти на диск и потом ровно также их читает, не нужно вставлять туда по новой элементы по одному. Тоесть если диск пишет, допустим, 250 мб/сек. То примерно с такой скоростью HArray может быть сериализован и десериализован с диска.

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

Получается нужна развилка отдельно под линукс, отдельно под виндовз.

Да, но их таких мест вроде немного.

Стабильность — признак мастерства. За 5 лет ничего не изменилось :)))))

# g++ HArray_insert.cpp
HArray_insert.cpp:1489:2: error: jump to label 'FILL_KEY' [-fpermissive]
  FILL_KEY:
  ^~~~~~~~
HArray_insert.cpp:488:12: note:   from here
       goto FILL_KEY;
            ^~~~~~~~
HArray_insert.cpp:552:10: note:   crosses initialization of 'uint32 keyValue'
   uint32 keyValue = key[keyOffset];
          ^~~~~~~~
я ж правильно понимаю, что если это все-таки сбилдить, и включить все оптимизации, то компилятор может тупо вырезать все ветки, которые ведут к этому гото?

Если не ошибаюсь, это неопределенное поведение.

не шарю c/c++, но судя по цппреференсу, это что-то еще хуже чем ub — стандарт говорит, что такой код даже компилироваться не должен. Что в таком случае оно будет выдавать с О3?

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

LABEL:
uint32 keyValue = key[keyOffset];
goto LABEL;

Я переписал (и закомитил) вот так и претензии у него к коду отпали.

uint32 keyValue;
LABEL:
keyValue = key[keyOffset];
goto LABEL;
goto LABEL;

goto это хорошо, особенно прыгать из одного if в другой. Перепиши по нормальному свой код =)

Его уже нереально переписать.
В 2016 году прилетели инопланетяне, оставили unhumanity logic код, показали землянам как надо писать такие контейнеры и улетели. Остается чесать тыковку и думать, почему это работает.
/Sarcasm Off/

Артем, Панк и Головатый, я думаю у вас достаточно уже занний, чтобы форкнуть эти поделки и дофиксать по человечески, а там уже и монгу потеснить и свой самолет прикупить :-)
Если че я инвестирую свою гробовую заначку :-))))

Мені справді цікаво погратися з цією структурою, але в такому вигляді як вона є це дуже складно. Принаймні для мене.

Trie я ніколи не писав, але колись сам реалізовував різні види дерев з усіма операціями, міряв у порівнянні з std::map та boost::hash_map, навіть підглядав щось у тих всередині. Приємно згадати :)

Если б ТС описал алгоритм, и доказал формально его корректность, можно было бы о чем-то говорить. Портировать алгоритм, который может иметь формальный баг, нет смысла.

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

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

Один из этих языков я презираю, а другой — ненавижу.

Это ты зря. Ценность языка на самом деле не в синтаксисе, а в наличии продвинутого компилятора для него. Люди закопали сотни человеколет, чтобы код после компиляторов Си/Си++ был максимально эффективным. А вот сколько на компилятор Раст потратили человеколет, неизвестно. Но явно меньше чем на Си/Си++.
Отсюда вывод, возможно для Раст лучше залинковать готовые бинарники скомпилированные С/С++ компиляторами.

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

Не вижу смысла об этом спорить. Я свой выбор сделал и в советах не нуждаюсь.

Люди закопали сотни человеколет, чтобы код после компиляторов Си/Си++ был максимально эффективным. А вот сколько на компилятор Раст потратили человеколет, неизвестно. Но явно меньше чем на Си/Си++.

В компиляторе раста такой же бекенд, как и в компиляторе clang. А скоро еще допилят бекенд gcc, тогда вообще збс будет.

Отсюда вывод, возможно для Раст лучше залинковать готовые бинарники скомпилированные С/С++ компиляторами.

Зачем раст линковать с тем, в чем скорее всего течет память и есть UB?

Зачем раст линковать с тем, в чем скорее всего течет память и есть UB?

Пруфы будут ? Вот код который чекает консистентность страниц памяти. Сверяет что каждый бит сошёлся в контрольных суммах. github.com/...​er/HArray/HArray_test.cpp
Этого кода могло бы и не быть, как в тысячах других проектах, но он есть. Его роль, чтобы качество работы программы, хоть на марсоход поставляй. Целый слой логики отвечающий за самодиагностику состояния контейнера в каждый момент времени.

Пруфы будут ? Вот код который чекает консистентность страниц памяти. Сверяет что каждый бит сошёлся в контрольных суммах. github.com/...​er/HArray/HArray_test.cpp

Можешь написать зачем эти биты чекать? Что именно это дает и где этот чек выполняется?

Можешь написать зачем эти биты чекать? Что именно это дает

Типичный баг с этим контейнером выглядит примерно так.
При вставке 7,854,123 ключа, что-то пошло не так. Допустим не дозаписали сегмент в блоке. Постепенно ситуация ухудшается, данные тихо кораптятся и при вставке 9,123,456 ключа процесс крашится или ключи перестают корректно читатся. Вот чтобы обнаружить точку где начались проблемы как можно раньше и существует этот код. Также он чекает висячие ссылки, блоки которые записаны, но не используются и нигде не фигурируют в пулах.

где этот чек выполняется?

Выполняется когда гоняют тесты и бенчмарки. Наиболее тяжелые кейсы, когда контейнер нужно разобрать по кирпичикам при удалении ключей. Начинается сложный процесс описанный в этом топике dou.ua/forums/topic/33788 И этот код помагает чекать, что после каждой итерации при сворачивании от сложного к простому, контейнер находится в полностью консистентном состоянии и готов для применения следующей итерации изменений.

Люди закопали сотни человеколет, чтобы код после компиляторов Си/Си++ был максимально эффективным.

>80% этого закапывания «сохранено» в виде LLVM и бэкенда GCC.

Отсюда вывод, возможно для Раст лучше залинковать готовые бинарники скомпилированные С/С++ компиляторами.

Ніт.

Допиливать до рабочего состояния его солянку из С и С++ у меня лично желания нет. Один из этих языков я презираю, а другой — ненавижу.
Я б портировал на Rust

С любым свеже-выпущенным процессором — производителем процессора поставляется компилятор С.

Кто в здравом уме и не будучи в состоянии наркотического одурения — будет поставлять с процессором компилятор Раста?

Так что, хипстеры могут продолжать развлекаться любимым Растом в своих песочницах и генерить свои «оупен-соурс» неоплачиваемые поделки сколько влезет. Вход в реальную индустрию (тy, что со специалистами и с деньгами) — Расту не грозит.

Можно пример процессора, под который не собирается Rust?

doc.rust-lang.org/...​stc/platform-support.html

Собственно, гарантированная поддержка — лишь для „Tier 1” платформ:
— ARM64 Linux (kernel 4.2, glibc 2.17+) 1
— 32-bit MinGW (Windows 7+)
— 32-bit MSVC (Windows 7+)
— 32-bit Linux (kernel 2.6.32+, glibc 2.11+)
— 64-bit macOS (10.7+, Lion+)
— 64-bit MinGW (Windows 7+)
— 64-bit MSVC (Windows 7+)
— 64-bit Linux (kernel 2.6.32+, glibc 2.11+)

На „Tier 2” собирается, но с „красными” тестами.

На „Tier 3”, может не собраться. Или даже если соберётся — (может) не запуститься (т.к., к примеру, не хватает памяти).

Т.е. внезапно на большинство свежевыпущенных мейнстримовых процессоров есть поддержка или Tier 1 или Tier 2. Это результат годного дизайна экосистемы компилятора — вместо того, чтоб самим пилить бекенд, взяли бекенд LLVM и получили бесплатную поддержку тонны платформ.

Кое-что требует допиливания (поэтому куча вещей или отсутствует, или лежит в Tier 3), но это место, где рынок голосует — put your time where your mouth is. Если не нашлось хотя бы одного красноглазика, который хотя бы запилит Tier 3 поддержку, значит платформа мертва, или настолько закрыта, что несовместима с идеологией Rust.

Скоро допилят gcc as backend, тогда вообще збс будет.

Так что не надо тут сказки рассказывать про «свежевыпущенные процессоры».

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

Я когда-то читал что умеет делать Си компилятор, так он умеет даже рекурсию разворачивать в циклы.

Я рад, что ты для себя открыл такую штуку как tail call optimization, которую изобрели еще в 70-х годах (как и все остальные крутые штуки в области computer science).

Кстати, есть языки, в которых нет циклов вообще (например, Scheme), и tail call optimization, это единственное, что позволяет в этих языках делать циклы.

Си/Си++ компилятор вне конкуренции

Давно уже не вне конкуренции. Можешь найти бенчмарки, на которых Rust стоит рядом с С и С++.

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

Умные люди давно поняли, что пилить тулчейн с нуля для каждого языка не получится, поэтому сейчас есть компоненты для построения тулчейны языка, например, LLVM, который используется Clang-ом для компиляции C/C++ и Rust-ом для компиляции Rust кода, предоставляя им практически одинаковые оптимизации (за вычетом оптимизации неопределенного поведения С/С++), и одинаковый набор поддерживаемых платформ.

Кроме того, в пятый раз напишу, что в добавок к LLVM бекенду, уже пилится альтернативный Rust бекенд на базе GCC, и оптимизации и платформы, которые поддерживает GCC, тоже будут доступны в Rust.

Давно уже не вне конкуренции. Можешь найти бенчмарки, на которых Rust стоит рядом с С и С++.

Если бы я написал контейнер который работает по скорости «рядом» с тем же std::map меня бы даже слушать не стали. Сдается мне что мало Расту приблизится к скорости С/С++ чтобы его вытеснить. Поскольку С/С++ это уже давно мейнстрим и стандарт.
Ну а синтаксис, С/С++ выбирают не за синтаксис, а за наработаную кодовую базу и возможность писать на нем низкоуровневый код.

Давно уже не вне конкуренции. Можешь найти бенчмарки, на которых Rust стоит рядом с С и С++.

Раст уже осилил что-нибудь похожее на «placement new»? Насколько я понял, нет.

А без этого, о каких вообще бенчмарках можно говорить?
Разве что, если сравниватъ с кодом, написанным полными нубами (они обычно и пишут эти публичные т.н. «бенчмарки») — которые понятия не имеют, как правильно писать производительный код на C/C++.

А потом, на основании этих т.н. «бенчмарков» — другие нубы рассказывают, что «модерн жаба уже быстрее плюсов».

Раст уже осилил что-нибудь похожее на «placement new»? Насколько я понял, нет.

Это бессмысленный вопрос, потому что в Rust нет конструкторов с понимании C++. Но мы можем написать функцию, которая проинициализирует указанный указатель так, как нам нужно. Возможно нам надо будет привести его через unsafe и всё. Вот пример поэлементной инициализации массива без копирования:

doc.rust-lang.org/...​-array-element-by-element

Но мы можем написать функцию, которая проинициализирует указанный указатель так, как нам нужно.

«Так как нам нужно» — то там где нужно/хочется Расту.
При этом, с выделением памяти (вызовом аллок) под капотом, под каждый чих.

Это не тот код, который может показать перфоманс.

Пример с вектором (Vec<T>) не катит, т.к.
«A vector is a densely packed array in memory, and it requires that all its element occupy the same amount of space. The size of the elements needs to be known at compile time. Trait objects don’t have a known size, so you can’t store them in a Vec.»

То есть, вектор объектов (не указателей на объекты, а именно объектов) — таким не создать.
(хотя, размер класса должен быть известен во время компиляции)

Пример с вектором (Vec) не катит, т.к.
„A vector is a densely packed array in memory, and it requires that all its element occupy the same amount of space. The size of the elements needs to be known at compile time. Trait objects don’t have a known size, so you can’t store them in a Vec.”

То есть, вектор объектов (не указателей на объекты, а именно объектов) — таким не создать.

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

Обсуждение 2020-го года:

„Why does rust need something like placement new”
www.reddit.com/...​thing_like_placement_new

Насколько я понимаю, текущее положение дел такое:
„the order before optimizing is the following:
— Create object.
— Allocate memory.
— Move object.
And swapping step one and two is difficult to the optimizer.”

В общем, не летает. О каком производительном коде тогда, вообще может идти речь?

Мы вернемся к placement new, ты сначала ответь на вопрос: dou.ua/...​sb_comments_forum#2158644

Мы вернемся к placement new, ты сначала ответь на вопрос: dou.ua/...​sb_comments_forum#2158644
Покажи пример раст кода, который из-за этого ограничения не скомпилируется.

Я не любитель раста, т.к. зачем тратить время на хипстерский язык — который сейчас популярен, а через 2 года о нём никто не вспомнит?
Таких языков всегда было дохрена и раст в этом ряду — далеко не первый и не последний.

То, что я видел — выглядело так:

trait Foo { }

pub struct A {}

impl Foo for A {}

fn test() -> Vec<Foo> 
{
    let generic_vec: Vec<Foo> = Vec::new();
    generic_vec.push(A {});
    return generic_vec;
}

Это должно быть, что-то типа плэйсмент нью (и поскольку Vec<Foo> выглядит, как вектор объектов, а не указателей — вероятно, так и есть).
И это не летает.

P.S. Ок, а такое катит?

pub struct A {}

fn test() -> Vec<A> 
{
    let generic_vec: Vec<A> = Vec::new();
    generic_vec.push(A {});
    return generic_vec;
}
Я не любитель раста, т.к. зачем тратить время на хипстерский язык — который сейчас популярен, а через 2 года о нём никто не вспомнит?

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

То, что я видел — выглядело так:
trait Foo { }

pub struct A {}

impl Foo for A {}

fn test() -> Vec<Foo> 
{
    let generic_vec: Vec<Foo> = Vec::new();
    generic_vec.push(A {});
    return generic_vec;
}
Это должно быть, что-то типа плэйсмент нью (и поскольку Vec выглядит, как вектор объектов, а не указателей — вероятно, так и есть).
И это не летает.

Разумеется, не летает. И это не имеет никакого отношения к placement new.

Trait (на русский переводится как «типаж», чтоб тебе было понятнее) — это не объект, это аналог интерфейса из других языков программирования (или абстрактного класса из C++). Он описывает какое поведение реализует структура, но не описывает какие данные в ней находятся. Из-за этого компилятору и вектору неизвестно сколько байт нужно зарезервировать, чтоб сохранить там данные — 0 байт (как в твоем случае), или 10 байт или 100 байт, или 10 килобайт.

В С++ есть такая же проблема, ты не можешь создать std::vector< IFoo > и класть в него экземпляры классов, котоыре реализует IFoo, потому что в векторе есть место только чтоб хранить сам IFoo, который занимает 0 байт.
Вернее, ты можешь, и вызовешь object slicing, со всеми вытекающими последствиями, когда Rust это запрещает на этапе компиляции, чтоб збс.

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

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

«Учить» — значит, использовать его для реального кода, т.е. в каком-то проекте. С другой стороны, зачем использовать в проекте какую-то хипстерищну-однодневку — когда есть надёжное и работающее.

С хипстерами я периодически сталкиваюсь (т.к. ими забита вся современная индустрия). Тянет такой в проект какой-нибудь пайтон, непонятно зачем — и пишет на нём ахинею, типа b = bytes(item['value'], 'utf-8') где летят эксэпшены и которую приходится править, чтобы работало.

И спрашивается, что челу мешало использовать язык/средства, в которых он флюент — вмеcто того, чтобы тащить в проект непонятно что и непонятно зачем?
То же самое и с растом.

П.С. Я в предыдущем комменте уже дописал кейс без трэйтoв — такое работает?

Выше тебе уже другой ответил оратор, это делается через MaybeUninit.

но компиляторы на Си/Си++ писали настоящие задроты еще тогда, когда над каждым байтом трусились как над последними штанами

От тех компиляторов ничего не осталось.
GCC прошёл десяток радикальных реформ, одно введение SSA чего стоит.

Ну и часто оказывается, что код после -Os быстрее, чем после -O3, за счёт сокращения объёма и соответственно улучшения кэширования.

Я когда-то читал что умеет делать Си компилятор, так он умеет даже рекурсию разворачивать в циклы.

Это сейчас в базе LLVM.

то Си/Си++ компилятор вне конкуренции, поскольку это десятки мегабайт алгоритмов по оптимизации в архиве.

Всё это в LLVM и бэкенде GCC, повторюсь.
Дело фронтэнда — отдать код в хоть как-то понятном виде, можно без оптимизаций.

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

Для него C компилятор есть? Пишут, что кто-то осилил прогнать через mrustc, сгенерировать аналогичный C код из Rust программы и дальше собрать C компилятором.

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

dou.ua/forums/topic/33788

Я до речі дивився твій код щоб зробити навколо нього інтерфейс типу мапи, щоб можна було щось типу
HArrayMap<string, string> m;

m["string1"] = std::string("string2");
робити, але без хеш-функції з коробки не вийде. І якщо хешувати об’єкти та контролювати час життя ключів та значень — це доволі багато коду.

Упростил тебе задачу.
Добавил методы врапперы:

bool insert(const char* key, uint32 keyLen, uint32 value);
bool getValueByKey(const char* key, uint32 keyLen, uint32& value);
bool hasPartKey(const char* key, uint32 keyLen);
bool delValueByKey(const char* key, uint32 keyLen);

Теперь чтобы передать std::string можно сделать както так.

std::string myKey = "blablabla";

HArray ha;
ha.insert(myKey.c_str(), myKey.length(), 555);

uint32 value;
ha.getValueByKey(myKey.c_str(), myKey.length(), value);

printf("%u", value);

ha.delValueByKey(myKey.c_str(), myKey.length());

Есть 2 варианта.
1. Написать пулл строк, где хранить строки с айдишниками. А в value хранить айдишник строки.
2. Хранить в value напрямую адресс строки (char*)value. Но такой вариант не подходит для 64х битных систем, value пока что 32 бита, поскольку я в основном использую в своем коде пулы и мне 4,2 млрд ключей и велью с головой.

1. Написать пулл строк, где хранить строки с айдишниками

Якщо їх зберігати як просто масив то час пошуку ключа раптом стане O(n) і мапі будеш програвати.

Якщо ж викорстатит ту саму мапу — в чому сенс тоді ще й твій контейнер брати?

2. Хранить в value напрямую адресс строки

Тут дві проблеми:
1. за різними адресами можуть бути ідентичні рядки.
2. рядок за оригінальною адресою може змінитися.

Що робити з типами які не можна просто скопіювати блоком, а треба викликати конструктор?

Не совсем понял.
Ты можешь на самом деле делать даже так

HArray ha;

std::string myKey = "blablabla1";
ha.insert(myKey.c_str(), myKey.length(), 555);

myKey = "blablabla2";
ha.insert(myKey.c_str(), myKey.length(), 555);

myKey = "blablabla3";
ha.insert(myKey.c_str(), myKey.length(), 555);

Итого у тебя в контейнере 3 ключа.
И также извлекать. Поведение такое же как у обычного Dictionary в какой нить джаве или дот нете.

Ти просто конвертував std::sting в char[555]. Таке дале не з усіма типами можна робити, наприклад якщо інкапсульовані вказівники.

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

struct Bla
{
    int* myValue;
    int* myValue2;
}
Может конвертнуться как ключ в 8 байт. Если ты в одном адрессном пространстве, то вполне себе уникальный ключ.

Якщо є конструктор копіювання то треба викликати його. І деструктор відповідно.

Хто буде робити копії за ось тими вказівниками і хто буде їх звільняти?

Ну Key/Value это аналог индекса в субд. Индекс это отдельная структура для поиска объектов (строк) по определенному ключу. Индекс строится рядом оригинальной структуры (таблица) и не участвует в удалении или создании объектов (строк) в ней.

Все так, але я ж те саме вже кілька разів повторив. Щоб скористатися твоїм контейнером в С++ коді треба:
— написати свою хеш-функцію, можливо для кожного типу даних
— знати як правильно робити копії ключів та значень в/з масиву байтів
— знати коли ключі та значення звільняються, конвертувати їх в правильний тип (інформація про який вже буде втрачена) і викликати деструктор

До того ж щоб просто замінити std::map у найпростішому випадку мені треба буде:
— написати ітератор для кожної можливої комбінації типу ключа та значення
— додати підтримку алокаторів.

Якщо говорити про чистий С то твій контейнер там має більше сенсу, але і порівнювати з мапою тоді не варто — мапа дає набагато більше функціоналу і робить більше.

Давай я как-то доберусь и сделаю value произвольной длины и тогда можно будет повторить полностью интерфейсы std::map.

Ось тут хороші приклади та посилання на документацію про те який мінімум треба зробити для свого stl-like контейнера — stackoverflow.com/...​ng-your-own-stl-container.

не надо так. В map<k,v> нет никаких значений произвольной длины, все значения занимают sizeof(v) байтиков. Посмотри уже наконец, как работает мапа, там несложно

sizeof(v)

Сейчас у меня sizeof(v) всегда 4 байта.
А сделать нужно чтобы можно было велью не только 4 байта записывать.

эх, думал тут про мотоциклы...А тут скукотень для которой и boost’а хватает.

Продолжаем тему с тестированием Артема, где Артем не смог вставить 80 млн ключей.
dou.ua/...​rums/topic/18849/#2044301

Я подебажил код, ожидаемо он упал потому что закончились пулы.
Сделал ресайз пулов динамически и залил изменения в master

На своей машине в твоем тесте я вставил 1.2 миллиарда ключей

По памяти у меня отожрало 18.3 гб.
(Оригинальный размер датасета:
1.2 billion * (4byte key + 4 byte value) = 9.6 гб)
Если у тебя на борту больше, сможешь вставить больше, вплоть до 4 млрд ключей.

Круто. Как только теперь это можно использовать на практике?

Це ідеальний код без багів який перемагає будь-що за будь-яких умов. А на практиці користуйтеся своїм попсовим std::map та іншими недолугими подєлками з тестами, документацією та білд-процесом.

Любой код идеален, пока к нему не добавляют тесты, документацию и билд-процессы.

Любой код идеален, пока

... його не запускають

У меня есть знакомый который работал в конторе которая занимается видеокодеками, писал как раз те самые автоматизированные тесты. Как ты думаешь, как они тестируют свой код ? Да очень просто. У них есть большой корпус не сжатых видео файлов самых разных типов и размеров и они их пропускают их все через видеокодеки, а потом смотрят что получается. Полный цикл их тестирования длится часами. Они не встроены в какието билд степы и тд.
Ровно также как и архиваторы тестируют. Пакуют корпус больших файлов, потом разжимают и смотрят что побитово все совпадает. Понимаешь, никто не пишет такие простые тесты «А что будет если ноль передали в качестве параметра». В этом нет смысла. Для таких проектов, с сложными алгоритмами, это не имеет смысла.

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

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

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

Це інтеграційні та/або E2E тести.

Они не встроены в какието билд степы

А юніт-тести є частиною білд процесу.

ты можешь сколько угодно рассказывать что есть баги

Ти можеш скільки завгодно розказувати, що багів нема.

Ну и я жду код, который крашит или показывает баги в моей либе

А я чекаю тестів.

Це інтеграційні та/або E2E тести.

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

Ты не согласен ? Ты собрался код архиватора или кей велью тестировать монкей юнит тестами типа а что будет есть неправильный ключ передали ? Твой подход просто не работает. А недостаток квалификации не дает тебе понять почему это не будет работать. Лол.

Коли у тебе є коробка радіодетальок то в процесі збірки радіо з них:
— перевіряємо кожну детальку — юніт-тести
— перевіряємо кожен вузол (блок живлення, антену, підсилювач, ...) - інтеграційні тести
— перевіряємо, що можна покрутивши ручку посунути стрілку на потрібну частосу і почути передачу саме на цій частоті — E2E тести.

Те що ти пропонуєше це зібрати радіо, а коли щось не працює то лізти перевіряти кожну детальку. Що і дорого, і довго, і показує незрілість процесів.

— перевіряємо кожну детальку — юніт-тести
— перевіряємо кожен вузол (блок живлення, антену, підсилювач, ...) - інтеграційні тести
— перевіряємо, що можна покрутивши ручку посунути стрілку на потрібну частосу і почути передачу саме на цій частоті — E2E тести.

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

Тебе показывают радио

Твоя ліба в найкращому випадку вузол. Сама по собі вона нічого не робить і має бути використана в реальній програмі щоб мати для мене користь. І цілком нормально очікувати, що був хоч якийсь контроль якості і відповідності заявленим характеристикам.

вывод что «либа сырая без тестов»

Ліба не викликає довіри і не має сенсу дивитися на неї доки не буде тестів.

Тебе показывают рабочуют либу которая прошла все E2E тесты

Де ці тести?

А ты предлагаешь тестирование отдельных резисторов, транзисторов и диодов.

Так, мені потрібні гарантії того, що базові компоненти належної якості і мають заявлену поведінку.

В этом нет никакого смысла.

В цьому лише сенс і є. Брати непойми що у використання, без тестів та документації — який в цьому сенс?

Тебе надо, можешь добавить такие тесты

Тобі треба щоб я серйозно сприймав твою лібу і спробував її використовувати — ти добавляй тести.

E2E тест имеет наивысшую ценность. Он показывает что продукт работает, не отдельные компоненты его, а весь продукт работает так как надо. Все части согласованы в своей работе.
Е2Е тест для контейнера, это вставка большого количества ключей и их правильное извлечение и удаление.
Нагрузочные тесты в 1600 строчек кода которые тестируют три метода insert/get/delete ты можешь найти в функции main.
Ты можешь запустить эти тесты. Можешь написать свои тесты и взять свои сценарии использования. Известных багов на сейчас — нет. Хотя сценарии использования запредельные, превысили миллиард ключей.

E2E тест имеет наивысшую ценность.

Вартість, а не цінність. Бо коли щось, що можна було зловити на етапі білду ловить E2E — це дуже дорого, з великим відставання і під час роботи над іншою вже задачою.

Известных багов на сейчас — нет.

За відсутності тестів так завжди буває.

Вартість, а не цінність. Бо коли щось, що можна було зловити на етапі білду ловить E2E — це дуже дорого, з великим відставання і під час роботи над іншою вже задачою.

Мне не дорого. Мне нормально. Кейс Артема я пофиксил за минут 15 и даже не залазя в код написал что пул закончился.
Любой баг в своем алгоритме я фикшу не более 2х часов. Мне главное найти сценарий, где мой код не отработает. И именно Е2Е тест наиболее замороченный и эффективный для выявления багов.
А юниттесты в моем кейсе (не в других проектах) почти бесполезны.

Мне не дорого. Мне нормально.

Але ж ти намагаєшся продати свою лібу не лише собі. Відповідно і виникають питання про відповідність заявленого реальності.

Я никому ничего не продаю. И даже не собираю пожертвования. Я просто говорю что я написал достаточно революционный алгоритм и подкрепил его открытым кодом, Е2Е нагрузочными тестами и гарантией отсутствия багов. В случае наличия багов (а если они не обнаружились при работе с миллиардом ключей в контейнере, то в обычном кейсе на неск миллионов ключей и говорить неочем) я пофикшу их очень быстро.

Я никому ничего не продаю

«Продаю» тут в сенсі не заробляння грошей, а пропозиції іншим скористатися твоїм кодом. Бо інакше для чого ця тема?

Дуже легко зробити репо з випадковим кодом і без тестів, а потім казати, що тести не потрібні і все ідеально — бо гарантія.

Е2Е нагрузочными тестами

Де покриття коду можна подивитися?

гарантией отсутствия багов

Як перевірити цю гарантію. На слово вірити не буду. Які тести можна запустити і побачити, що код робить те, що від нього очікують?

Які тести можна запустити і побачити, що код робить те, що від нього очікують?

Запускаешь проект и ждёшь минут 15 прохождения всех тестов.

Запускаешь проект

Що це словосполучення означає?

У тебе там написано Windows & Linux. Ок:

git clone github.com/Bazist/HArray.git
cd HArray
make

вгадай що далі.

Мейк файл вроде как чинил. Специально Линукс машину для этого искал чтобы потестировать. Не сбилдидось ?

На вінді:

> nmake
NMAKE : fatal error U1064: MAKEFILE not found and no target specified
Stop.

На лінуксі:

$make
make: *** No targets specified and no makefile found.  Stop.

Так вот мейкфайл
github.com/...​ob/master/HArray/makefile

Ты в правильной директории make запускаешь ?

Ты в правильной директории make запускаешь ?

Чітко слідую інструкціям в документації.

Ок, скорей в твоём случае

git clone github.com/Bazist/HArray.git
cd HArray/HArray
make

Тобто від документації могла б бути якась користь?

Ок, а як щодо купи варнінгів в «ідеальному коді»? — pastebin.com/mcrWHkVD

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

Да и смотрю ворнинги в основном ругаются на дебажные printf

Ворнинги ничего не значат в данном случае

Відсутність тестів теж нічого не означає. Як і відсутність документації. Та і взагалі може не компілятися — це мало що значить, код же ідеальний. Ось і гарантія.

Корректность кода тестируют здесь более основательными методами

Тобто ніякими.

Ну і для чого такий коди без тестів, без документації та ще й з варнінгами? Ти за той час поки намагаєшся мене переконати в ідеальності свого коду вже давно міг покриття хоча б 70% зробити. І не на словах, а прямо в репорті покриття показати — ось воно.

Код идеальный багов нет, потому что те драконовские нагрузочные тесты с кучей разных проверок все давным давно повычищали. Чай не автопилот теслы тестируем, а простой контейнер для ключей. Он покрыт тестами на 100% вдоль и поперек.

Код идеальный багов нет

Але це не точно — нема ніяких тестів щоб це підтвердити.

Он покрыт тестами на 100%

Але це не точно — репорт з покриттям відсутній.

та ще й з варнінгами

Ты бы те варнинги почитал хотябы. На printf ругается. Очень смешно.

Ты бы те варнинги почитал хотябы.

На даному етапі мені достатньо того що вони є. Після цього вірити в те що «код ідеальний» якось не раціонально.

Ты бы те варнинги почитал хотябы.

Та хоч на scanf — компілятор тобі явно каже, що твій код не ідеальний як мінімум.

E2E тест имеет наивысшую ценность. Он показывает что продукт работает, не отдельные компоненты его, а весь продукт работает так как надо.

Как бы не имеет. Это тест, в котором под капотом десятки или даже сотни компонентов, который показывает pass/fail сигнал. Если pass — все збс. Если fail — хуево, и чо теперь с этим делать? Надо проверять компоненты по отдельности и разбираться какой именно из них косячит, сейчас посмотирм тесты более низкого уровня, oh shit...!

Полный цикл их тестирования длится часами.

Вот когда нет юнит тестов, циклы тестирования и занимают часы и даже недели в случае если это ручное тестирование. Юнит тесты должны выполняться за считанные минуты (и тут счёт на тысячи тестов будет).

Но ты прав в одном — end-to-end тест с правильными данными способен покрыть 100% кода, если конечно в коде нет сложных превентивных проверок на например инъекции в данные.

Но ты прав в одном — end-to-end тест с правильными данными способен покрыть 100% кода, если конечно в коде нет сложных превентивных проверок на например инъекции в данные.

Именно так и есть. Только таким тестам можно доверять. Юнит тесты, да, можно добавить просто как демонстрация какой-то функциональности, но не более.

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

Ти схоже просто не розумієш для чого потрібні юніт-тести. Бо сказане звучить як «компіляцію можна додати як демонстрацію, але не більше».

потрібні юніт-тести.

Я тебе уже сказал как тестируют видеокодеки и архиваторы. Пойди продай им свои юниттесты. Более того, кадр который сделает упор на простенькие юнитесты, никогда не напишет и не отладит такой сложный проект.

Я тебе уже сказал как тестируют видеокодеки и архиваторы

А я тобі сказав чому не варто витрачати час на лібу у якої навіть юніт-тестів нема.

Пойди продай им свои юниттесты.

Для чого це мені? У них є продукт який задовольняє, або ні мої вимоги як користувача. Як вони це роблять там у себе і чи тестують взагалі мене не хвилює.

Але ж ти намагаєшся продати не продукт, а код, лібу навколо якої треба ще буде писати продукт. І відповідно виникає питання які гарантії якості, де хоча б тести і покриття?

кадр который сделает упор на простенькие юнитесты, никогда не напишет и не отладит такой сложный проект.

Зі «складним проектом» ти сильно вперед забігаєш. Спочатку хоча б юніт-тести додай.

Зі «складним проектом» ти сильно вперед забігаєш. Спочатку хоча б юніт-тести додай

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

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

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

Для себе можеш робити як хочеш, але якщо плануєш мене зацікавити використовувати свій код то маєш показати тести і покриття хоча б.

радио работает в самых замороченных сценариях очевидно же что все его мелкие части тоже работают как надо

У тебе не радіо, а усього лише один з його елементів. Сама по собі твоя ліба не дає ніякої цінності користувачам доки навколо неї не написано код програми. А мені щоб використати твій компонент потрібні гарантії роботи відповідно заявленим характеристикам.

Ти ж пропонуєш зібрати радіо з твоїм компонентом і потім перевіряти чи працює воно, а як ні — лише тоді перевіряти твій компонент. Усе якось догори ногами і в самий затратний спосіб.

Ти ж пропонуєш зібрати радіо з твоїм компонентом і потім перевіряти чи працює воно, а як ні — лише тоді перевіряти твій компонент. Усе якось догори ногами і в самий затратний спосіб.

А ты как хотел ? Если у нас на работе хотят использовать Редис, то запихивают его в наш сценарий использования, именно с нашими данными и смотрят как он себя ведёт. С какой скоростью работает.
Я могу лишь гарантировать что мой код корректно работает на всех моих нагрузочных сценариях и известных багов не обнаружено, даже если вставляли сотни миллионов и даже миллиард ключей.

у нас на работе хотят использовать Редис

Продукт з багатьма відомими випадками використання, з документацією та підтримкою. Не соромся вже, порівнюй свою лібу з віндою чи лінуксом, там теж мабуть тестів не пишуть через свою крутість (ні).

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

А, так у тебе ліба спеціально лише для гарантованих тобою сценаріїв. Якісь інші дані чи послідовність операцій і все, гарантія втрачається?

А, так у тебе ліба спеціально лише для гарантованих тобою сценаріїв. Якісь інші дані чи послідовність операцій і все, гарантія втрачається?

Дело в том, что контейнер по своей сути достаточно прост для тестирования. Он даже не многопоточный. Просто пишешь ключ и велью и читаешь. Не понимаю почему ты такую проблему раздул. Например DniproDB это полноценная база данных, там багов много, есть ограничения, ее тяжело тестировать. Сценариев много использования, многопоточность и вот это вот все.
Но key/value это самая надёжная часть. Она действительно без багов и я в ней уверен.

контейнер по своей сути достаточно прост для тестирования

І де тести?

Не понимаю почему ты такую проблему раздул

Тому що є певний когнітивний дисонанс коли хтось стверджує про ідеальний код без багів і в той же час не може зрозуміти для чого потрібні юніт-тести.

і в той же час не може зрозуміти для чого потрібні юніт-тести.

Так ты же сам расписал эволюцию тестов.
Самое простое пройти юнит тесты.
Сложнее интеграционные.
И самое сложное Е2Е.

Я пропустил юнит тесты потому что они ровно нихрена толком в моем случае не выявят. Но выявит тяжёлая артиллерия вроде интеграционных или е2е, типа чекать контрольные суммы, лить ключи до аут оф мемори, лить ключи самой разной природы и длины, чекать каждый вставленный ключ и тд.

Так ты же сам расписал эволюцию тестов.

Яка ще еволюція? Я тобі розписав для чого потрібні види тестів які використовують найчастіше.

Я пропустил юнит тесты потому что они ровно нихрена толком в моем случае не выявят

Крім випадків коли виявлять і не треба буде дебажити код щоб знайти елементарну помилку чи тайпо.

Крім випадків коли виявлять і не треба буде дебажити код щоб знайти елементарну помилку чи тайпо.

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

Элементарных помилок там уже давно не осталось

Це треба довести.

Будем руководствоваться презумкцией невиновности. Багов нет до тех пор пока не доказано обратное.

:D

Тоді і правда будь-який код без документації та тестів є ідеальним та без багів.

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

Ты занимаешься тем что выдумываешь себе проблемы. Ворнинги, тесты не такие, документация не такая на контейнер с тремя методами и тд. А что если контейнер у тебя не будет работать. У меня работает на миллиарде, а у тебя наверно план 50 млрд ключей вкачать.

Короче не занимай время, я спать.

Розумієш, ти прийшов продавати свій «ідеальний код без багів», а коли до нього виникли питання почав вигадувати виправдання замість виправити. За той час, що ти намагаєшся довести, що юніт-тести чи документація не потрібні ти міг би їх вже написати.

І я особисто не бачу ніякого сенсу навіть пробувати користуватися лібою в якій мало того, що відсутні тести та документація, так ще і автор на всі вказані проблеми доводить що вони не важливі.

Навіть уявимо хтось ризикнув твоїм кодом скористатися, включив його в свій білд. Бац — варнінги, білд падає. Всьо, на цьому твого «ідеального» коду позбуваються і забувають про нього.

Я до речі дивився твій код щоб зробити навколо нього інтерфейс типу мапи, щоб можна було щось типу

HArrayMap<string, string> m;

m["string1"] = std::string("string2");

робити, але без хеш-функції з коробки не вийде. І якщо хешувати об’єкти та контролювати час життя ключів та значень — це доволі багато коду.

Але маючи таке можна було б вже порівнювати на тих сценаріях де мапу та інші колекції використовують.

але без хеш-функції з коробки не вийде

А зачем хешфункция, если HArray не требует хешфункций ? В этом его фишка, он сортирует и упаковывает ключи без всяких хешей, что является предметом нестабильности в хештаблицах (коллизии).

Можно сделать конвертацию как-то так. Правда строка должна быть выровнена по 4м байтам.
std::string str = «bla bla bla»;
uint32*key = (uint32*)str.c_str();

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

Если я оберну твой harray в некий ipc процесс, сделаю маршаллинг для выборки ключей (для потоко защищённости и множества клиентов), то так как

uint32*key = (uint32*)str.c_str();

Ключ у тебя поинтер на сырые данные, и каждый новый запрос будет аллоцировать вычитанные из сокета ключи в новое место в памяти — harray не сможет детерминированно вычитать ключ foo с разных запросов?

Не совсем понял схему. HArray нужно передать три значения
поинтер на ключ uint32*, длину ключа и велью. И он прочитает все данные с этого поинтера и вставит в контейнер.

Не совсем понял схему. HArray нужно передать три значения
поинтер на ключ uint32*, длину ключа и велью. И он прочитает все данные с этого поинтера и вставит в контейнер.

Я еще не разбирался с твоим проектом построчно =)
Но если есть два ключа
std::string key1="foo"
std::string key2="foo"

Они идентичны? Даже если c_str() указывает на разные «foo» ?

Да. Контейнер копирует ключ и проверяет дубликаты. Если это дубликат ключа, то велью апдейтится.

Контейнер копирует ключ и проверяет дубликаты

Як він це робить якщо у нього нема інформації про тип ключа, а відповідно і про те як правильно зробити копію. Наприклад у мене ключем буде наступний тип:

struct key {
   void* pv;
   char* pc;
   ...
};

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

Я копирую массив байт

В С++ цього не достатньо. Я там спеціально написав вказівники. Тобто мені ще треба буде вручну робити копії усіх об’єктів всіх можливих типів.

Але навіть не це найгірше. Як ти будеш викликати деструктор для «масиву байт»? Ось ті вказівники які для твого коду насправді байти є адресами пам’ять за якими треба звільнити.

Не совсем понял.
Ты мне передал допустим обьект как ключ 64 байт к примеру.
Я их себе в контейнер скопировал. После того как ты ключ из контейнера удалил, я в контейнере 64 байт удалил.

Ты мне передал допустим обьект как ключ 64 байт к примеру.
Я их себе в контейнер скопировал.

Деякі з тих байтів були вказівниками чи вкладеними об’єктами які треба правильно копіювати.

После того как ты ключ из контейнера удалил, я в контейнере 64 байт удалил.

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

А зачем хешфункция

для того щоб наступне працювало:

sting s1 = "key1", s2 = "key1";

if (m[s1] == m[s2]) {...}

А з твоїм кодом мені треба:
— написати свою хеш-функцію
— десь зберігати ключі
— десь зберігати значення
— відстежувати час життя ключів та значень

Мапа та інші контейнери все це роблять з коробки.

Не совсем понятно. Этим кодом ты будешь сравнивать values

m[s1] == m[s2]

Если ты написал простинький пул, где велью это айди строк в этом пуле, то никаких проблем писать такой код нет.

Если ты написал простинький пул, где велью это айди строк в этом пуле,

Поки забудемо про те що мені ще й «простенький пул» писати треба буде і спитаю — як цей пул організувати? Просто масивом/списком, чи може std::map використати?

Убрал все Warnings. Можно забирать master.

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

ПС: По ходу дела допустил одну очепятку и тесты это мигом выявили, исправил.

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

Можно уточнить в каких проектах?

В 2 моих проектах (полнотекстовый движок и документоориентированная субд)
и еще пару человек мне писало по имейлу, спрашивало что да как.

Можно ссылочки?

А где используются сии поделия, в каких продуктах?

Наконецто. А почему ты пятницу пропустил ?

Сделал ресайз пулов динамически и залил изменения в master

І тест додав який підтверджує, що тепер не буде крешитися за таких умов?

Добавлять тест на вставку 1,2 млрд ключей ?
А у std::map такой тест например есть ?
Потому что у меня на таком обьеме он крашится и виснет.

Добавлять тест на вставку 1,2 млрд ключей ?

Як інтеграційний тест — чому б і ні?

А у std::map такой тест например есть ?

Я тобі вже показував де подивитися які юніт-тести є для мапи.

Як інтеграційний тест — чому б і ні?

И что это даст ? А если у когото память закончится ? И почему именно 1,2 млрд ключей. 2 млрд я не смог вставить, у меня на ноутбуке память закончилась. Может лучше 8 или 16 млрд ключей ? Чтобы каждый юзер кричал что моя либа крашится, не разобравшись про аут оф мемори эксепшин в тестах ?

И что это даст ?

Це дасть підтвердження того, що код працює як і до змін.

А если у когото память закончится ?

У кого це «кого-то»?

И почему именно 1,2 млрд ключей.

Не знаю чому ти саме таку кількість запропонував.

Может лучше 8 или 16 млрд ключей ?

Може і краще. Ти як автор тесту маєш розуміти який саме сценарій перевіряєш.

Потому что у меня на таком обьеме он крашится и виснет.

А ты эксэпшены ловишь?

Ловлю, но в этом мало смысла. Это Fatal Error который по хорошему приведет к перегрузке приложения. (пример с out of memory, если память закончилась, то делать уже ничего не получится)

Добро пожаловать на СУбд-строительные верфи. Господин Прокофьев пока не подтвердил свою подписку на следующую пятницу. Ты ещё можешь успеть запрыгнуть на алтарь.

Он регулярно лечится водичкой, но видать вода не живая, а мертвая :-)

Мде. Если в эмигосрачах у тебя ещё был шанс пресмыкаться из под табуретки, то в техническом топике просто проедуться катком по твоей тонкой вайтишной натуре )

Это опять какая-то дичь про лабрадора??? :-)

візьмем цю моду винесення в топчік
ти дорікаєш std::map за відсутність

6. Сохранятся на диск на уровне скорости работы дисковой системы — не умеет

і відповідно вихваляєшся наявністю цього в тебе
dou.ua/...​rums/topic/18849/#2136000

Якщо оце та геніальна функція збереження github.com/...​ster/HArray/HArray.h#L220 —

Велью фиксировано действительно 4 байтами, потому что чаще всего это поинтер на объект.

то скажи, будь-ласка, яка користь із файла з поінтерами на об’єкти, стрічки, будь-що, якщо це поінтери. Де збережені дані?

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

«ві нє понімаєтє, єто другоє»

6. Сохранятся на диск на уровне скорости работы дисковой системы — не умеет

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

Мне это удается, поскольку я сбрасываю на диск готовые пейджи скопом. Если у тебя какая-то говноструктура, которая представлена миллионом мелких объектов в графе который ещё нужно обойти, то твоя структура нихера не оптимизирована для работы с диском. Мой же контейнер сериализируется/десериализируется на уровне 100 мб/сек с обычным шпиндельный диском.

Мой же контейнер сериализируется/десериализируется на уровне 100 мб/сек с обычным шпиндельный диском.

Ты сейчас хвастаешься или жалуешься?

Конечно хвастаюсь. У меня готовые мегабайтные страницы памяти пишутся на диск. И также читаются. Получить такое в обычной мапе или хештаблице совсем не просто. Собственно поэтому они и не умеют сбрасываться и подыматься с диска на максимальной скорости винчестера.

то скажи, будь-ласка, яка користь із файла з поінтерами на об’єкти

Я написал на HArray два движка СУБД, которые работают с диском.
В качестве value сохраняется offset в файле.

Сама по себе твоя идея переложить сериализацию на контейнер черевата. Ты никогда не сможешь решить общий случай сериализации объекта, со всеми вложеностями, циклическими ссылками и тд. Это не тривиальная задача. В дотнете есть мембервайсклон. Но и он нихера не работает, а бежит по верхам. Потому мне твой бомбеж на счёт велью не понятен.
Ты пытаешься решить задачу которая за скобками Кей велью контейнера

Сама по себе твоя идея переложить сериализацию на контейнер черевата. Ты никогда не сможешь решить общий случай сериализации объекта, со всеми вложеностями, циклическими ссылками и тд. Это не тривиальная задача. В дотнете есть мембервайсклон. Но и он нихера не работает, а бежит по верхам. Потому мне твой бомбеж на счёт велью не понятен.
Ты пытаешься решить задачу которая за скобками Кей велью контейнера

«а как дисал, а как дисал»

зверху в топіку

Легендарный супероптимизированый алгоритм, который реализует весьма сложные Trie структуры данных и топчет вот эти вот эти ваши самые реализации ассоциативных массивов std::map, glib, dictionary.net и прочью заморскую попсу в разы, а то и на порядок.

Ты услышал что тебе написали ?
Как ты в дикшинари собрался сериализовать например объекты с циклическими ссылками, а потом десериализовать чтобы все встало в памяти как надо автоматом ?

Ты услышал что тебе написали ?
Как ты в дикшинари собрался сериализовать например объекты с циклическими ссылками, а потом десериализовать чтобы все встало в памяти как надо автоматом ?

а ти побачив чим ти хвалишся і що насправді у тебе?

Ты приписываешь дикшинари и мапам функциональность, которую они _впринципе_ не могут реализовать правильно. Кстате это хороший был бы вопрос на собеседование, узнать у кандидата почему сериализовать десериализовать объекты в общем случае нифига не тривиальная задача. Думаю всяких профнепригодных слоупоков можно было бы с лёгкостью отсеивать. О таком в этих ваших литкодах не напишут. А теория графов тут просто кричит

Ты приписываешь дикшинари и мапам функциональность, которую они _впринципе_ не могут реализовать правильно.

serde.rs
Out of the box, Serde is able to serialize and deserialize common Rust data types in any of the above formats. For example String, &str, usize, Vec, HashMap are all supported. In addition, Serde provides a derive macro to generate serialization implementations for structs in your own program.

common Это примитивные типы. Они мне нахер не нужны в субд. А ты реализуй в общем случае, чтоб любой объект. Пример с циклическими ссылками я приводил.

common Это примитивные типы.

serde вполне работает с композитными типами

Пример с циклическими ссылками я приводил.

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

Потому что я не вижу смысла это реализовывать как половинчатое решение. А в всяких дикшинари и мапах оно именно так и работает. Вплоть до того что мы сериализовать ниче не будем пока не заимплементите сами функцию как ваш объект правильно сериализовать. Если так, то какая разница где его сериализовать. И зачем это делегировать мапе.

И зачем это делегировать мапе.

Это хороший вопрос. Зачем сувать всю возможную функциональность в один класс? Есть такая штука как single responsibility principle. Один класс отвечает за сериализацию, другой за эфективное хранение данных в памяти и организацию доступа к нему и т.п.

Вплоть до того что мы сериализовать ниче не будем пока не заимплементите сами функцию как ваш объект правильно сериализовать.

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

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

Кстате кинь ссылку на исходники функции которая сериализирует хешмап в расте.

github.com/...​rde/src/ser/impls.rs#L374

Если там сбрасываются готовые страницы (для этого там должен быть рукопашный менегер памяти)

Тебе для этих целей не нужен рукопашный «менегер памяти», тебе нужен memory-mapped file.
У тебя этого, разумеется, нет, ты просто открываешь файл через fopen и фигачишь туда свои внутреннее представление данных.

если там обходят циклопический граф и сериализирует элементы по одному то тормознутая академическая имплементация.

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

А точно ли в сотни?
Вот рассмотрим вырожденный случай когда элемент один байт и они раскиданы по всей памяти таким образом, что чтение никогда не будет происходить из кеша.
А в качестве сторедж пусть будет ssd на pcie.

Это Артем ошибся примерно на два или три порядка. Обход десятков миллионов объектов разбросанных по памяти в классическом академическом варианте Node(Parent) может быть очень и очень больно. На счёт SSD немного не согласен, не обязательное условие. SSD будет выигрывать прежде всего за счёт отсутствия позиционирования механической головки. Но если мы в лоб пишем гигабайты ровно по дорожке диска, то там скорость на обычном шпиндельном диске может достигать до 500мб/сек. Именно с такой (Макс) скоростью HArray весь сериализируется и десериализируется с диска. Что очень удобно для старта СУБД, она просто подымает страницы памяти с диска в рам, не вставляя элементы по одному в контейнер по новой.
И здесь же элементарно реализуется уже известный LRU, ибо отслеживать какие нужны страницы в рам а какие лучше вытеснить на диск тоже очень просто.

Обход десятков миллионов объектов разбросанных по памяти в классическом академическом варианте Node(Parent) может быть очень и очень больно.

Если твоя задача это сериализация хеш структуры, то в мапу подставляется свой аллокатор который выделяет память под ноды из своих собственных «страниц» памяти из адресного пространства процесса, и дальше эти страницы можно дампить на диск как хочется через fwrite. Если имеет значение порядок данных, то есть некая связанность — это тоже в аллокаторе можно разрулить (грубо говоря где выделять место под ноду)

Ok, допустим записать страницы тебе удастся. Прочитать их как ? Как сказать стандартной мапе что вставлять по новой ничего не надо. Используй уже готовые десериализированные страницы памяти.

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

. Но если мы в лоб пишем гигабайты ровно по дорожке диска, то там скорость на обычном шпиндельном диске может достигать до 500мб/се

Да ладно!
с хардваре видимо знаком по наслышке ?

Одиночный HDD 7200 пишет 250MB/s на внешних дорожках в лучшем случае. На внутренних скорость падает вдвое.
То есть в среднем диск будет выдавать 160MB/s
и это в идеальных условиях.
например www.ixbt.com/...​exos-x18-18tb-review.html

Да ладно!
с хардваре видимо знаком по наслышке ?

ні, просто бенчмаркає у вакуумі, без зливання кешів

Ждал ответа про о enterprise 10/15k rpm, но видимо и так достаточно lol

В Дельфі колись серіалізація-десеріалізація компонент на формах (а потім і датамодулях) була зроблена. І навіть працювала.

Про серіалізацію підграфу об’єктів я диплом писав :)

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

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

Перше — «визнаність» твоєї «крутої реалізації» дещо надумана. Знають її лише на тих ресурсах де ти сам її піарив, та і то знають більше через твій стиль спілкування, а не через крутість реалізації.

Друге — не треба бути автором «крутих реалізацій» щоб задавати питання. А питання до твого коду є — чому він не компілиться без ворнінгів, чому крешиться, чому в нього треба лазити руками кожного разу коли треба щось «оптимізувати», чому розкидані магічні значення, ...

Третє — ти перший почав «піднімати цю тему» та «витрачати час» і мав би бути елементарно вдячним за те, що люди витрачають час і дивляться на твій код. І не просто дивляться, а знаходять проблеми, задають питання по темі та висловлюють сумніви.

И не подымай эту тему.

Після того як ти припиниш розказувати нісенітниці про ідеальний код та те як твоя реалізація удєлує мепи та хеш-таблиці.

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

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

з тобою через твою геніальність напевне в тімі ніхто не працює :-), ти сам собі тім

У порядних конторах про косметику тебе просто засміють.
Твій код може бути геніальним (на самом деле нет), але при PR review там є банальні, автоматичні, жесточайші і бездушні automatic checks.
1. компілюється з warnings — до побачення, помилка, приходь, коли пофіксаєш
2. cyclomatic code complexity check — функція на 1300 рядочків — до побачення, помилка, приходь, коли пофіксаєш
3. security check — лазаєш по пам’яті грязними ручонками, конвертуєш int/pointer направо і наліво — будь любєзєн, внеси ці зауваження в exception/ignore list (ну, тобто всю твою програму) — до побачення, помилка, приходь, коли пофіксаєш
і т.д.

І це ще до того, як колеги почнуть твій код розглядати.

Почему я и сказал что ты формошлеп. Работаешь по хомячковым шаблонам своего Лида. Мне пох* на хомячковые стандарты. Я буду использовать гоуту, длинные функции и прочий арсенал настоящего джедая который пишет алгоритмы уровня кернела.
Для галеры я пишу код который проходит все ревьювы и стандарты. Это делать проще чем писать действительно крутой оптимизированный код.
И такому глупому хомячку как ты этот скил недоступен от слова совсем.

Почему я и сказал что ты формошлеп. Работаешь по хомячковым шаблонам своего Лида. Мне пох* на хомячковые стандарты. Я буду использовать гоуту, длинные функции и прочий арсенал настоящего джедая который пишет алгоритмы уровня кернела.
Для галеры я пишу код который проходит все ревьювы и стандарты. Это делать проще чем писать действительно крутой оптимизированный код.
И такому глупому хомячку как ты этот скил недоступен от слова совсем.

це все adhominem і мимо каси, ліда блін, бггг

хомячковиє стандарти, бггг

«алгоритмы уровня кернела» — ти хоч кернел бачив (Windows/Linux)? Тебе би Linus змішав з гівном, або просто проігнорив би за такий код

Я буду использовать гоуту, длинные функции и прочий арсенал настоящего джедая который пишет алгоритмы уровня кернела

Я сам код «рівня кернела» не писав, писав навколо нього, але довелося його побачити і навіть трошки подебажити у певній кількості (Windows 7/8). І код той написано чисто (з використанням SAL — docs.microsoft.com/...​quality/understanding-sal) і компілиться він без варнінгів. І покрито його тестами теж дуже добре.

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

Якби не хочеться переходити на особистості, але ти переоцінюєш свою експертність та унікальність.

Код чого тобі показати? Це ж не я в цьому топіку розказую про ідеальність свого коду.

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

Именно так. Есть реализация, есть о чем говорить. Есть экспертиза. Нет реализации — давай досвидания.

Я рассказываю про идеальность своего кода, поскольку он хорошо работает

Варнінги при компіляції, segfault під час робити та необхідність ручних правок просто для того щоб зберігати дані іншого розміру — це що завгодно, але не ідеальний коди і не код який добре працює.

segfault під час робити

Последний сегфолт я видел когда память закончилась, когда пытались вкачать 300 миллионов ключей. Вот бросал ссылку на машинках помощнее вкачивали миллиард ключей без сегфолтов.
Причем на таких объемах всякие стдмапы и денсы дохнут как мухи, но не мой алгоритм. Ибо ему пох* на коллизии он создан на запредельные объемы данных.

Це круто, але історії лишаються історіями. І доки у тебе не буде тестів та прикладів використання вірити їм буде не кожен.

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

Хуцпа

«Хуцпа» — определяется как «особо циничная, подлая, наглая ложь», «верх цинизма и наглости, парализующий оппонента».
Другие определения, которыми часто обозначают понятие «хуцпа», — сверхнаглость, бессовестность, бесцеремонность, нахальство, хамство, нетерпимость по отношению к другим, дерзкое и наглое лицемерие. Часто эти определения употребляют с приставкой «сверх-» и другими словами, подчеркивающими превышение всяких норм и выход за рамки установленного: «сверхнаглость», «суперложь», «экстраординарная наглость», «необыкновенное нахальство», «неслыханное вранье», «невиданная дерзость», «запредельная бесстыжесть», «небывалая бесчестность» и так далее.
...
Американские судьи Алекс Козински и Юджин Волок приводят объяснение употребления этого слова в английском языке на примере анекдота: «Юноша, который убил обоих родителей, чтобы получить наследство, в суде просит о помиловании, ссылаясь на то, что он круглый сирота».

===
по решті пунктів Oleksandr Golovatyi сказав нижче — dou.ua/...​rums/topic/18849/#2135965

Аффтор, а ты случайно раньше не зажигал на sql.ru в ветке ПТ?
уж больно ник и слог знакомый

и на sql.ru и на ixbt жег напалмом под ником bazist.

точно, помню что на ПТ был базист (в линке аффтора на гитхаб увидел bazist и сразу вспомнил) и тоже всякую дичь нес
я вот хотел проверить свою мысль и зашел на sql.ru — выяснилось что ПТ уже почил в бозе, не выдержал бедняга срачей :)))

да ну, там же вменяемое сообщество, гениев не приемлют :)))

Похоже мы все в колбасных топиках имели дело с проффесиональным троллем ))

из него тролль как известно из чего пуля. Он искренне верит в свои поделки.

Это и есть искусство быть троллем — на серьёзных щщах задвигать всякую чушь и убедить всех что ты сам в неё веришь. :))

Это «чушь» работает. Так что пецтеть можно что угодно, но на гите все есть и запускается ровно в 2 клика.
И после этого все вопросы кто тролль, а кто дело говорит, моментально отпадают.

тут увы другйо случай: для троллинга несколько лет педалить какую то говноподелку — чересчур.

Так я не понял. Ты в очередь на жертвоприношение величайшим алгоритмам становится будешь ?
Если честно, для меня шкурка галерного архитектора наименее ценна. Все знают что нормальный архитектор грамотно борется с сложностью в проекте, а галерный архитектор наоборот, вносит максимальное количество своей глупости, чтобы раздуть проект до максимально возможных сроков. Как по штату сотрудников, так и по срокам реализации.

:) бомбеж оценил. Но по сути то есть что сказать? За 5 лет получилось внедрить свою поделку хоть куда то, хоть в приватбанк продать?

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

вопросов больше нет :)))

Да я. Но нужно учитывать что оба ресурса российские.
И на обоих ко мне отношение было предвзято политическое.
Особенно на

ixbt

где в технических темах
я общался с отморозками которые спонсируют ДНР/ЛНР.
Именно поэтому я ушел с обоих этих форумов.

Шо опять? Там ошибки в коде, автора кто только(в том числе и я немного) ссаными тряпками не гонял :)

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

как успехи? За 5 лет сколько процентов рынка бд подмял? Кому из лидеров рынка свое поделие продал? А хоть той, ошибки в коде на которые тебе 5 лет назад пофиксил? :)

Нет там никаких ошибок в коде. Успокойся уже. Нагрузочные тесты все прекрасно показывают. Были тесты (не я делал) миллиард ключей вставляли.

На счёт рынка, если ты хочешь торговать, гоу в ларек с шавермой. Это теоретически-практические работы в компьютер сцаинц.

а їсти ти також будеш

компьютер сцаинц

?

Это мое хобби, могу себе позволить

Были тесты (не я делал) миллиард ключей вставляли.

В 32х битовом процессе при том что под винду доступно только 2Gb виртуального адресного пространства на процесс.

docs.microsoft.com/...​ed/virtual-address-spaces

/LARGEADDRESSAWARE

+ Структура частично занимается компрессией данных
+ Никаких проблем пересобрать под 64 разряда

/LARGEADDRESSAWARE

Ну будет 3Gb, ты даже не вместишь туда миллиард uint32_t. Как всегда спиздел про миллиарды, даже не подумав.

+ Никаких проблем пересобрать под 64 разряда

Проблемы я тебе выше указал, оно работать у тебя не будет.

Ну будет 3Gb,

Не 3 а 4 Гб. Учи матчасть.

Проблемы я тебе выше указал, оно работать у тебя не будет.

Я как понял ты уже разобрался в алгоритме и вынес вердикт ?
Пока нет, мне виднее как и что там работает.

Не 3 а 4 Гб. Учи матчасть.

Точно-точно? Есть такое подозрение что ты ошибаешься :)

И если немного подумать, то вот как будет в 32-битном процессе работать взаимодействие с кернелом если юзерспейс отдать 4gb?

Если округлить будет почти 4. Кернел не отъедает гиг, ест мелочь на адрессные таблицы для win32.

Google говорит что эта опция даёт до 3gbyte.
Ты уверен что знаешь как округление работает?

Наверно у меня какой-то другой Гугл
This is why the /LARGEADDRESSAWARE flag was introduced into the Portable Executable (PE) file format header. The LAA flag indicates to the operating system that this 32bit application is „certified” by its developers to handle full 4GB of memory.

codekabinett.com/...​handle full 4GB of memory.

Тебе перевести?
Этот флаг говорит системе что процесс может работать с полными 4gb.

По твоей же ссылке

To understand what this means we need to go back in time. When the Windows operating system was 32bit only, it was able to address a maximum of 4GB of RAM memory (theoretically, effectively only ~3GB). Any application instance running on 32bit Windows was only allowed a maximum of 2GB of memory. The remaining memory was reserved for the operating system to run its own processes and other applications.

32-битный процесс в 32-битной системе никаким образом не может получить 4gb.
3 вот твоя цифра.

32-битный в 64-битной я без понятия. Я не знаю как работает MMU в этом случае, например можно ли держать два поддерева страниц в одном процессе, одно с 32 а другие для кернела с 64. Подозреваю что нет, и ограничение все равно будет 3gb.

Но я не специалист, а ты же специалист по округлениям, расскажи как это работает.

Но я не специалист, а ты же специалист по округлениям, расскажи как это работает.

Старт адрессов в заголовке Win32 (PE32) процесса начинается с 400000. Тоесть тебе доступно 4гб — 400кб.

По факту, оси нужно еще меньше места в твоих 4гб.
Представь что тебе нужно написать кернел операционной системы для 32х бит. Все хорошо, потому что ты можешь хендлить все 4гб в поинтере, все тебе доступно. Но есть проблема. А что если твое приложение должно взаимодейстовать с ОС ? На какие адресса ты должен отправлять колы внутри своей песочницы ? Для этого, когда тебе выделяют память тебе ее выделяют не всю, а чуть-чуть оставляют как раз на маппинг внутренних вызовов функций к внешним. Те самые 400кб. Другими словами когда процесс дергает win32 функцию, он дергает свой внутренний адресс, а таблица уже указывает что код который должен выполнятся, находится за рамками песочницы в 4гб.

Пришёл адрес в кернел из юзерспейса. Каким образом кернел получит доступ к данным по адресу?

Кернел насколько я понимаю всегда замаплен в адресное пространство юзерспейса.

Пришёл адрес в кернел из юзерспейса. Каким образом кернел получит доступ к данным по адресу?

Для кернела твой процесс не более чем песочница в контейнере на 4 гб виртуальной памяти.

Кернел насколько я понимаю всегда замаплен в адресное пространство юзерспейса.

Да. Кернел знает, что если ты обращаешся внутри своей песочницы на адресс меньше 400000 то ты по сути дергаешь экстернал кол Win32 api. Именно поэтому первые 400 килобайт своего адрессного пространства тебе не доступны.

Нет, подождите.
Вот пошёл сисколл с адресов буфера в кернел. Этот буфер надо отправить отправить в сетевую карту.
Как и где ты его будешь копировать?

Что значит как и где ? Для Кернела все страницы памяти открыты для чтения. Кернел видит, что пришел указатель на буфер с такойто песочницы, лезет туда (вычисляем этот адресс: начало адресса процесса + адресс буфера) и читает все данные.

Что значит открыты?
Есть многоуровневая таблица страниц. Процессор по ней ходит. Чтобы кернел мог читать из адресного пространства процесса и свои данные одновременно, надо чтобы и кернел и юзерспейс были одновременно замаплены в одно виртуальное адресное пространство.

Кернел на то и кернел, что он стоит НАД всеми песочницами. Он ими управляет и для него нет никаких защит памяти на страницах. Эти правила существуют для песочниц. Как получить точный адрес буфера я написал. Адресс процесса + Адресс буфера который пришел с песочницы процесса = Физический адресс в ОЗУ

Здрасьте приехали.
Давай ты сначала разберёшься как на низком уровне это работает.

Давай ты сначала разберёшься как на низком уровне это работает.

Нет, давай уж ты разбирайся.
Поскольку это работает, буферы передаются с процессов на сетевые карты и тд. А как это работает, это уже тебе разбираться, с моими обьяснениями или без.
Лучше без.

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

вычисляем этот адресс: начало адресса процесса + адресс буфера

1) адреса
2) Что такое «начало адресса процесса»?

Именно поэтому первые 400 килобайт своего адрессного пространства тебе не доступны.

1. 0×400000 это 4MiB, а не «400 килобайт». Мелочь, но в данном контексте существенно.

2. Первые 4MB пропускаются для удобства ядра, которое туда может мапить, например, первые 1MB физической памяти, даже не давая процессу доступа к ним.

3. В x86 дизайне сами каталоги страниц должны лежать в той же памяти. На них вместе с сопутствующими структурами ядра тратится до ~5%, это ~200MB от 4GB.
Если бы эта была какая-нибудь SystemZ, там такого ограничения нет. Но x86 тупее.

4. Если процессу отдано 3.8GB, то чтобы ядру хоть что-то сделать полезное — придётся выкидывать страницы процесса на диск, работать, а потом закидывать обратно. Работа дорожает в разы. И вообще при 1.5GB физической памяти уже рекомендуют всем переходить на следующую ступень (64 бита), иначе возня со всякими double bounce buffers замедляет всё и вся.

4. Если процессу отдано 3.8GB, то чтобы ядру хоть что-то сделать полезное — придётся выкидывать страницы процесса на диск, работать

Все верно, но конкретно в моем случае это обычное консольное приложение, которое максимум выводит что-то на консоль. Простыни экстернал либ не импортирует, потому может использовать вполне все 3.8 гиг в 32х битном процессе

Все верно, но конкретно в моем случае это обычное консольное приложение, которое максимум выводит что-то на консоль.

Из-за него всем прочим придётся подвинуться и ужаться, во главе с ядром.

В общем, это аццкая перверсия и пользы с неё ноль. 64битку не зря придумали.

of RAM memory (theoretically, effectively only ~3GB).

Это приблизительное слишком приблизительное.
Сам подумай. Если ОСи нужно АЖ 1 гб из твоего адрессного пространства, то как раньше работали машинки на винде с 64 мегабайтами ОЗУ на борту. И это НА ВСЕ. По факту оси нужно отьесть с твоей памяти на кернел совсем крохи.

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

. Если ОСи нужно АЖ 1 гб из твоего адрессного пространства, то как раньше работали машинки на винде с 64 мегабайтами ОЗУ на борту.

Как можно быть столько лет погроммиздом и не понимать чем отличается виртуальное адресное пространство от физической памяти?

Читать научись контекст. Физически оси нужно намного меньше гига с твоего адрессного пространства.

Какой именно?
Ты в курсе что ОС тоже растут и жрут память. Драйвера там всякие.

Что-то меня уже начало утомлять.
Вернемся к первоначальному посту. Почему я считаю что 4гб (округленно) а не 2гб или 3гб как писал Горчак и о том, в какую сторону я округляю.

ibb.co/F3jDDpD

Ось одала больше чем 3,8 гб с флагом /LARGEADDRESSAWARE

Дальше уже разбирайтесь с Горчаком наедине. Ты сверху Горчака, или Горчак сверху тебя. Это уже как вам там интересно.

Фу таким быть

Ну извините. Кстате тебе плюс, за адекватное общение и попытку разобраться. Надеюсь Прокофьев к следующей пятнице начистит отполирует шкурку (хотябы копнет по верхам trie). Я на своем алтаре к следующей пятнице хочу увидеть по крайней мере ухоженную тушку галерного архитектора.

И что там случилось в конце, любопытства ради? Исключение или ты на ноль проверить забыл?
А sizeof указателя точно 4 байта?

Точно 4, x86 сборка
Дальше краш приложения, нужно экскпшин в c++ ловить

Ну значит порядка 200 мегабайт ОС на твоей системе. Сделать какой-нибудь драйвер который полгига зааллоцирует и все.

2Gb сделали по умолчанию не просто так. Есть shared memory, есть file mapping, создание потоков и стеков для каждого потока. Для каждого действие необходио линейное виртуальное адресное пространство. Место под всё это резервируется ОС. Всё равно тебе эту память никто не даст для работы, не зависимо от того что ты там считаешь или насчитал.

Всё равно тебе эту память никто не даст для работы, не зависимо от того что ты там считаешь или
насчитал

ibb.co/F3jDDpD

Отдает 3.8 гиг из коробки

Ну т.е. ОС всё равно забрала себе 300Mb, а не 400Kb. И при этом ты не можешь выполнить ни одного системное действия, ни замапить расшаренную память, ни даже создать поток, ни открыть динамически DLL. Такое себе достижение. Именно поэтому этот ключь не дефолтный, он подразумевает что разработчик понимает что он делает.

Ну а теперь вернёмся к миллиардам (именно во множественном числе) записей? Опять знаменитое бубно-сжатие пространства для бетоно-метров, теперь уже для памяти процессов под виндой? :D

Ну а теперь вернёмся к миллиардам (именно во множественном числе) записей? Опять знаменитое бубно-сжатие пространства для бетоно-метров, теперь уже для памяти процессов под виндой? :D

Я же писал. Не я даже тестировал. У меня были канадские архитекторы из Белл на ставке QA

Читай.
forum.ixbt.com/...​c.cgi?id=26:43056:545#545

К слову там жалуются что удаление у меня не реализовано. И я потом его таки реализовал. И как реализовал. Это настоящий алгоритмический шедевр.

Я же писал. Не я даже тестировал. У меня были канадские архитекторы из Белл на ставке QA
Читай.
forum.ixbt.com/...​c.cgi?id=26:43056:545#545

З таким самим успіхом можеш перечислити регалії Artyom’а і Oleksandr’a — з переписуванням їхніх контор — Amazon, Microsoft, GoDaddy, Tableau і т.д. (про мої контори скромно умолчім, я анонім і ніхто)

І як ти відповідаєш тому QA? Нєбось подякував?

forum.ixbt.com/topic.cgi?id=26:43056-20
Ні, написав тому прославленому архітекту
«Вы меня уже начинаете утомлять своей тупостью.»

А, он оно чьо :-)

Насколько я понимают все это будет в адресном пространстве процесса, в тех двух гигабайтах.

2 гигабайта именно я так понимаю серьезной причины нет. Скорее на заре показалось хорошей идеей поделить пополам. Потом, гуглится что ещё покрывается знаковым интом.

Насколько я понимают все это будет в адресном пространстве процесса, в тех двух гигабайтах.

Да, просто нужно различать caging который имеет стандартная библиотека и в основном она тусуется в нижних 2Gb и системные вызовы, которые имеет доступ к любому виртуальному адресному пространству процесса.

Потом, гуглится что ещё покрывается знаковым интом.

Именно так, весь фан начинался когда использовалась арифметика указателей, а указатели оказывались знаковыми. Слишком много легаси кода не работало. Например скомпиленное Win32S приложение из 3.11 должно было работать вплоть до Windows 7 в режиме совместимости.

Второй момент named shared memory. Например, «базовики» делали именно таким образом поддержку PAE (когда процессор в 32 битовом режиме мог адресовать >4Gb физической памяти) в процессах. Создавались shared memory по 256-512Mb в большом количестве и по-очередно мапились в процесс и вымапливались старые, когда нужен был доступ к этой памяти. А те 2Gb — это как раз то место куда ОС мапит такие вещи по дефолту, чтобы не мешать хипу: MapViewOfFile()/UnmapViewOfFile().

Также люди которые понимают как это работает — делали ballooning памяти через VirtualAlloc(...,MEM_RESERVE,...) — когда процесс при старте может разметить себе виртуальную память под свои нужды без выделения памяти, и затем мапить туда куски системной памяти для работы по нужным адресам. Для этого никаких опций компилятору давать не нужно было — это работает из коробки, если выйти за пределы стандартной библиотеки.

techcommunity.microsoft.com/...​ysical-memory/ba-p/723674 — там для сервера вінди цікаво розповідає чувак (шле привіт нам з далекого 2008).
Звичайно, що можна написати свій менеджер пам’яті, не такий перебірливий до ресурсів.
Я думаю що це задача на декілька днів для справжнього майстра!

вінди цікаво розповідає чувак

это ж Марк Русинович, его Windows Internals должна быть как библия для тех кто серьезно под винду пишет
Но по правде говоря тяжело у меня эта книга шла :)))
7я редакция покрывает современные версии винды
docs.microsoft.com/...​sources/windows-internals

Не 3 а 4 Гб. Учи матчасть.

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

Я как понял ты уже разобрался в алгоритме и вынес вердикт ?

Зачем мне весь алгоритм? Если ты пишешь говнокод, который хранит поинтеры в uint32_t вместо uintptr_t, то я могу только тебе посочувствовать.

Т.е. стека у тебя нет

Стек в моем адрессном пространстве. Занимает аж 1 мб, если не изменяет память.

там в адресное пространство клиента мапируются мегабайты dll’ек,

Осталось разобраться сколько мегабайтов длл мапируется к HArray которые вызывает new да delete и иногда чтото на консоль выводит.

Зачем мне весь алгоритм?

Незачем тебе, здесь я согласен.

Нет там никаких ошибок в коде.

чувак, тобі не бракує хуцпи брехати, коли всі ходи записані і на 5 році виявляється, що структура не вміє хендлити неіснуючі ключі, тупо повертає 0
dou.ua/...​rums/topic/18849/#2134680

Нагрузочные тесты все прекрасно показывают. Были тесты (не я делал) миллиард ключей вставляли.

нагрузочні тести працюють в одній функції, там де init/insert/get/delete/destroy

як тільки розносиш їх в різні закутки і починаєш робити отаке
dou.ua/...​rums/topic/18849/#2135157

1) точно такий же рядок, але за іншою адресою — ключ буде інший?
2) переписати рядок за адресою str — ключ лишається той же?

так одразу видно де зачітив і що структура тупо по можливостям не здатна конкурувати з std::map, чи Python dict

Успокойся уже.

вот такі да :-)

одразу видно де зачітив і що структура тупо по можливостям не здатна конкурувати з std::map

Так, заявляти про неї як заміну мепам/хеш-таблицям це дещо нахабно. Але чисто теоретично може бути задача коли треба швидко ключ->ідентифікатор знаходити. І тоді за умови що клієнт:
— сам реалізує хеш-функцію
— пам’ятає усі ключі
— гарантує існування об’єктів раніше доданих у колекцію
— гарантує незмінність об’єктів раніше доданих у колекцію

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

я правильно розумію, що ключі та значення в цій структурі можуть бути лише числами і лише користувач розбирається як їх інтерпретувати?

Саме так. Він реалізував доволі оптимальний спосіб збереження значень фіксованого розміру. В поточній реалізації це 32-розрядні значення наскільки я розібрався.

Нет, ключ может быть переменной длины. Для этого при вставке передается длина ключа. Велью фиксировано действительно 4 байтами, потому что чаще всего это поинтер на объект.
Но это можно переделать, просто в моих сценариях мне это не нужно.

Легендарный супероптимизированый алгоритм, который реализует весьма сложные Trie структуры данных и топчет вот эти вот эти ваши самые реализации ассоциативных массивов std::map, glib, dictionary.net и прочью заморскую попсу в разы, а то и на порядок.

а насправді

Велью фиксировано действительно 4 байтами, потому что чаще всего это поинтер на объект.
Но это можно переделать, просто в моих сценариях мне это не нужно.

Я написав

Він реалізував доволі оптимальний спосіб збереження значень фіксованого розміру

на що ти відповідаєш

Велью фиксировано действительно 4 байтами

Наче ж одне й те саме?

Так а че 4 а не 8? Ты уже в Azure и AWS не найдешь x32 виртуалок вообще, все x64, даже ARM.

тобто я можу використовувати як ключ рядки?

Да, ключ это любой массив байт любой длины выровненный по границе в 4 байта (в целях быстродействия)

чувак, тобі не бракує хуцпи брехати, коли всі ходи записані і на 5 році виявляється, що структура не вміє хендлити неіснуючі ключі, тупо повертає 0
dou.ua/...​rums/topic/18849/#2134680

*Фейспалм*
Какие будут следующий ошибки ?
Ошибки комментариев в коде ?

*Фейспалм*
Какие будут следующий ошибки ?
Ошибки комментариев в коде ?

ах, то для тебе це мєлочь? :-)
це у нас тут фейспалм 5 років тому і зараз знову
не диво написати тести, які вставляють і одразу читають задані значення із якогось масиву, а от на реальних задачках такі симульовані тести уже побоку
та блін, навіть простим читанням твого коду баги знаходяться, я мовчу вже про всілякі сегфолти, що були в людей раніше

На реальных задачах, по крайней мере те что у меня под рукой сейчас
std::map и hastable ___вообще___ не подходят по ____функциональности____

Остальное мне уже не интересно.
Баги иди в своем формошлепстве ищи.
Ты слишком т/глуп чтобы понимать как работают такие вещи. Иди нещасный LRU переучивай к собеседованию по 20 кругу (чего кстате меня и бомбануло. Люди до лру не могут додуматься, а некоторым рассказали и они забыли к следующему собесу).

На реальных задачах, по крайней мере те что у меня под рукой сейчас
std::map и hastable ___вообще___ не подходят по ____функциональности____
Остальное мне уже не интересно.
Баги иди в своем формошлепстве ищи.
Ты слишком т/глуп чтобы понимать как работают такие вещи. Иди нещасный LRU переучивай к собеседованию по 20 кругу (чего кстате меня и бомбануло. Люди до лру не могут додуматься, а некоторым рассказали и они забыли к следующему собесу).

хи-хи, гляди, як тебе заїло

тепер по пунктам
1. я хз, які у тебе реальні задачі, але твоя бібліотека обмежена і з багами
2. я не формошльоп, а ти хужеформошльопа — бо у тебе синдром Даннинга-Крюгера помножений на віндузятництво программінга
3. як бачиш, не глупий — розковиряв і потестив твій код (хоча я на C/C++ дуже давно не писаа), знайшов ще один баг — вот ти і злішся
4. на реалізацію LRU з віддебажженям і проходженням всіх тестів у перший раз у мене пішло 90 хв
5. запиляй LRU тут і розкажеш потім, скільки це зайняло часу — leetcode.com/...​ms/lru-cache/description . Має бути набагато швидше, ніж тут свій недороблений код захищати :-)

3. як бачиш, не глупий — розковиряв і потестив твій код (хоча я на C/C++ дуже давно не писаа), знайшов ще один баг — вот ти і злішся

Какой баг ? Это максимум тех депт, а минимум вкусовщина.

Уровень анализа у вас царапина на сопле истребителя. Это тех депт максимум.
Возвращать 0 вместо поинтера на объект если объект не найден.

Уровень анализа у вас царапина на сопле истребителя. Это тех депт максимум.
Возвращать 0 вместо принтера на объект если объект не найден. Не позорься

HArrayInt повертає uint32, 0, але не поінтер
ти читати мої комменти і свій код не вмієш
dou.ua/...​rums/topic/18849/#2134680

не позорся

HArrayInt повертає uint32, 0, але
не поінтер

Ты не можешь конвертнуть 32 бита в 32 бита в 32х битном процессе ?
(uint*)value

Печаль.

Ты не можешь конвертнуть 32 бита в 32 бита в 32х битном процессе ?
(uint*)value
Печаль.

1. Примітивно працюєш і намагаєшся увільнути.
2. Свого коду не знаєш.
Ти тестуєш запихання int‘ів, а не pointers
github.com/...​aster/HArray/Main.cpp#L87
3. у теперішній реалізації неможливо відрізнити, чи прочитався 0 по ключу, чи цього ключа немає. Бо «вкусовщина» супералгоритму.

3. у теперішній реалізації неможливо відрізнити, чи прочитався 0 по ключу, чи цього ключа немає. Бо «вкусовщина» супералгоритму.

Если для тебя критичен этот 0, используй следующую функцию.

github.com/...​ray/HArray_hasPartKey.cpp

Она проверяет есть ли ключ в контейнере.
Возвращает true/false. В отличии от бинарных деревьев и хештаблиц, может чекать ключи не только на есть ключ/нет ключа, но и есть ли вообще любой ключ который подходит под заданный шаблон. Функция работает за константное время, где константа это длина переданного шаблона О(1).

PS: Не пиши мне больше. Я вижу что ты решил взять меня измором своей тупостью.

Если для тебя критичен этот 0, используй следующую функцию.
github.com/...​ray/HArray_hasPartKey.cpp
Она проверяет есть ли ключ в контейнере.
Возвращает true/false. В отличии от бинарных деревьев и хештаблиц, может чекать ключи не только на есть ключ/нет ключа, но и есть ли вообще любой ключ который подходит под заданный шаблон.

посібо

Тепер перепиши testHArrayInt, щоб перед кожним getValueByKey воно дьоргало hasPartKey.
Запусти тести. Що буде — ой, уже не таке швидке, як раніше.

PS: Не пиши мне больше. Я вижу что ты решил взять меня измором своей тупостью.

я тільки почав, не треба твою хуцпу вважати моєю тупістю

тепер по ось цьому питанню дай відповідь
dou.ua/...​rums/topic/18849/#2135372

він там відповів вже (побіг за попкорном)

Тепер перепиши testHArrayInt, щоб перед кожним getValueByKey воно дьоргало hasPartKey.

Если бы я был говнокодером вроде тебя, то наверное так бы и написал. Но я же не говнокодер.
Поэтому getValueByKey переписываю специально для тебя за 5 минут, так чтобы абсолютно не потерять в скорости.

uint32 getValueByKey(uint32 key, bool& isExists)
	{
                isExists = true;

		HeaderCellInt& headerCell = pHeader[key >> BLOCK_BITS];
		uint32 rightPart = (key & BLOCK_SIZE);

		switch (headerCell.Type)
		{
		case 1:
		{
			if (headerCell.Code == rightPart)
			{
				return headerCell.Offset;
			}

			break;
		}
		case 2:
		{
			DoublePageInt* pPage = pDoublePages[headerCell.Offset >> 16];
			if (pPage)
			{
				DoubleValueCellInt& valueCell = pPage->pValues[headerCell.Offset & 0xFFFF];

				if (headerCell.Code == rightPart)
				{
					return valueCell.Value1;
				}
				else if (valueCell.Code2 == rightPart)
				{
					return valueCell.Value2;
				}
			}

			break;
		}
		case 3:
		{
			uint32 offset = headerCell.Offset + rightPart;

			MultiplyPageInt* pPage = pMultiplyPages[offset >> 16];
			if (pPage)
			{
				MultiplyValueCellInt& valueCell = pPage->pValues[offset & 0xFFFF];

				if (valueCell.Code == headerCell.Code)
				{
					return valueCell.Value;
				}
			}

			break;
		}
		};
               
                isExists = false;
		return 0;
	}
Возвращает флаг isExists найдено\не найдено.
Не благодари.
Если бы я был говнокодером вроде тебя

чувак, май на стримання, тут твій засраний код на GitHub висить, я ж там ковиряюся, бо у мене на цьому тижні приступ доброти і агрономії, аналіз як це на добрива перетворити

Возвращает флаг isExists найдено\не найдено.
Не благодари.

не буду, але хотів

тепер додай перевірку на isExists в тести
стало швидше? :-)

і т.д., ця низькорівнева реалізація без допилювання напильником і обв’язки перевірками купи фунцій, обв’язками alloc/destroy memory і т.п. — може бути швидкою і коректною тільки у вакуумі бенчмарків

в ріл-лайф її пустити — себе не поважати

Мне уже перестает быть интересным этот топик на доу.
За 5 лет существования этой темы, я помню единственный баг (не косметика) нашел канадский архитектор контрактор на ixbt. Я пофиксил этот баг за минут 15, но это был реальный баг в имплементации алгоритма, провтыкал одно место.

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

Начни писать юнит тесты. Пока их нет, твой проект работает по happy-path. С тестами сам найдешь несколько десятков багов :)

Начни писать юнит тесты. Пока их нет, твой проект работает по happy-path. С тестами сам найдешь несколько десятков багов :)

Видишь ты тоже не понимаешь специфику проекта.
Когда ты вставляешь десятки миллионов ключей в самых разных комбинациях, а потом удаляешь их по одному, разбирая структуру по винтикам до самого основания, пропустить баг крайне тяжело. Каждая строчка в коде покрыта тысячи если не сотни тысяч раз в разных комбинация. Ты просто не дойдешь до конца бенчмарка (который к слову длится минут 20 полной нагрузки на структуру),
если там будет хотябы один баг.

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

Легко пропустить, если ворочаешь десятками миллионов, но не дошел до 70 миллионов, как я ниже продемонстрировал :)

. Каждая строчка в коде покрыта тысячи если не сотни тысяч раз в разных комбинация.

Як ти збирав статистику покриття, яким кодом?

За 5 лет существования этой темы, я помню единственный баг

dou.ua/...​rums/topic/18849/#2044301

Там у тебя еще вроде с сегфолтом падает при 70 миллионах ключей, уже пофиксил?

Мне уже перестает быть интересным этот топик на доу.

канєшно, якщо за всяку муру і недоробки, провтики, проскакування гострих кутів і тд тебе постійно макають в твоє творіння — то «художніка каждий может обідєть» :-)
але хуцпи при тому...

Какой баг ? Это максимум тех депт, а минимум вкусовщина.

:-D, блін, я з тої хуцпи не можу

5. запиляй LRU тут і розкажеш потім, скільки це зайняло часу — leetcode.com/...​ms/lru-cache/description . Має бути набагато швидше, ніж тут свій недороблений код захищати :-)

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

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

ти рядок покажеш, чи будеш пілотірувати далі високо словоблудієм?
dou.ua/...​rums/topic/18849/#2135372

НЕ ИНТЕРЕСНО имплементить простые задачи

Вибач, але починати доведеться з простих. До того ж ти сам заявив про три різні реалізації LRU які зробив за 15 хвилин. Мені особисто цікаво подивитися на них.

а це що таке?
github.com/...​ray/HArray_insert.cpp#L23
mapping string <=>uint32?
а чого uint32*, а не char*?

uint32 HArray::insert(uint32* key,
					uint32 keyLen,
					uint32 value)

Причому ключ фіксований до 64 байт?
github.com/...​ster/HArray/Main.cpp#L831

const char STR_KEY_LEN = 64;

А як на рахунок string <=> string?

const char STR_KEY_LEN = 64;

Это в бенчмарке задается на строках какой длины будем тестировать.
В данном случае берутся рандомные строки в 64 символа.

А як на рахунок string <=> string?

Не совсем понял ?
char* str = «hello world»;
uint32 value = (uint32)str;

Для 32х битного процесса (даже на 64х разрядной системе) должно сработать.

Не совсем понял ?
char* str = «hello world»;
uint32 value = (uint32)str;

Для 32х битного процесса (даже на 64х разрядной системе) должно сработать.

вот я от тоже не поняв, я думав, що там можна string<=>string,
але там нікуди контент value не копіюється, тобто я очікував, що всередині insert буде strcpy, чи memcpy, а там тільки таке
github.com/...​ay/HArray_insert.cpp#L114

pContentPage->pContent[contentInde