про память. без коллизий хранится по 1 значению на бакет, бакет обычно - связный список, то есть укзатель + значение, + указатель на первый элемент списка. значит в тестовом примере как минимум 2 инта и 2 указателя на один элемент(16 байт для 32 бит и 24 для 64битной системы). бакеты могут хранить длину (+4 или 8 байт). кроме того хэш стабильно выделяет +30% места для уменьшения коллизий. так что в 64 битном случае получаем 32 метра на миллион элементов. Это если я ничего не забыл. Кроме того при добавлении по одному GC может не реалочить память, а оставлять промежуточные хэши, которые освоюодятся на следующем проходе GC. + ваши погрешности измерений.

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

спасибо, это было б крайне полезно и интересно

дерево нужно для бинарного поиска, оно позволяет хранить массив пар ключ-значение в отсортированном по ключу виде, следовательно поиск по такому массиву будет log(n)

std.container содержит красно-чёрные деревья и банарихип

ага, действительно можно, это будет быстро видимо

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

https://dlang.org/phobos/core_memory.html#.GC.collect

https://dlang.org/phobos/core_memory.html#.GC.collect

не помогло, но спасибо

ага, действительно можно, это будет быстро видимо

самая медленная реализация, но хранится только ключ и значение import std.stdio; import std.algorithm; import std.array; struct MyHash(K, T) { static struct Pair { K key; T value; } Pair[] data; // TODO rbtree ptrdiff_t find(K key) const { // TODO binary find foreach(i, val; data) if (val.key == key) return i; return -1; } void insert(K key, T value) { // TODO rbtree.insert auto idx = find(key); if (idx >= 0) data[idx] = Pair(key, value); else data ~= Pair(key, value); } T opIndex(K key) const { return data[find(key)].value; } ref T opIndex(K key) { return data[find(key)].value; } auto opIndexAssign(T value, K key) { insert(key, value); return value; } K[] keys() const @property { return data.map!"a.key".array.dup; } T[] values() const @property { return data.map!"a.value".array.dup; } } struct Data { float x, y, z; } void main() { MyHash!(uint, Data) aa; aa[13] = Data(3.14, 2.7, -1); aa[15] = Data(0, 1, 0); writeln(aa[13]); writeln(aa.keys); writeln(aa.values); MyHash!(string, int) bb; bb["hello"] = 13; bb["world"] = 42; writeln(bb["hello"]); }

а стандартные ассоциативные массивы вроде на скорость ориентированы

а стандартные ассоциативные массивы вроде на скорость ориентированы

да, к скорости то как раз вопросов нету. потестирую сейчас тогда ваш и другие варианты

ну мой вариант это просто пример и где TODO нужно код переписать, ещё нужно добавить удаление и остальные методы из стандартных AA

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

ну мне только добавление и поиск надо, а туду вижу, подумаю, как это сделать

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

в Ди всм алгоритмы встроенные норм?

ну да

а стандартные ассоциативные массивы вроде на скорость ориентированы

если не ошибаюсь, конечно

ну да

эт да, но как всегда в угоду одному страдает что-то иное

вариант, сохраняющий память просто реализовать (собственно пример), а вариант быстрый сложно, соответственно это хорошо, что в стандартной поставке сложный вариант

вариант, сохраняющий память просто реализовать (собственно пример), а вариант быстрый сложно, соответственно это хорошо, что в стандартной поставке сложный вариант

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

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

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

а, массив тюплов типа. а как тут вот так затраты на поиск посчитать?

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

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

бинарный поиск

бинарный поиск

а, понял, дошло

... bool sortBeforeInsert = true; bool isSorted = false; void sort() { data = data.sort!"a.key < b.key".array; isSorted = true; } ptrdiff_t find(K key) const { if (data.length == 0) return -1; enforce(isSorted, "binary find can work only on sorted range"); size_t a=0, b=data.length-1; do { auto c = (a+b)/2; stderr.writeln(data, " find ", key); stderr.writeln("current c == ", c, ", data[c] == ", data[c]); if (data[c].key == key) return c; else if (data[c].key > key) b = c; else a = c; } while(a != b); return -1; } void insert(K key, T value) { auto idx = find(key); if (idx >= 0) data[idx] = Pair(key, value); else data ~= Pair(key, value); isSorted = false; if (sortBeforeInsert) sort(); } ...

ну это тоже на вскидку

ну это тоже на вскидку

ого, буду разбираться

чёт накосячил с бинарным поиском)

ptrdiff_t find(K key) const { if (data.length == 0) return -1; enforce(isSorted, "binary find can work only on sorted range"); ptrdiff_t a=0, b=data.length-1; do { if (data[a].key == key) return a; if (data[b].key == key) return b; auto c = (a + b)/2; if (data[c].key == key) return c; if (data[c].key > key) b = c; else a = c; } while(b - a > 1); return -1; }

чёт накосячил с бинарным поиском)

слегка да, вкуриваю как раз

каждый раз как в первый раз

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

это плохо кончается

ну "спорт" жи

=)

там много граблей, вроде обработки повторяющихся, нкератных длин, отсутствующих элементов

в вашей версии точно есть переполнение инта в 32 битной версии и массиве больше 2 гигов

на (a+b)/2

уффф

не спорю, что там косяки

https://dlang.org/phobos/std_range.html#.SortedRange

там нет find, но есть lowerBound, которой хватит для задачи

да и вообще хорошей идеей будет хранить сортированный массив в SortedRange

Кстати, хотел спросить. Пайп он где? В оперативной памяти хранится?

это что-то типа стека в плане организации?

какой пайп? из std или vibe?

а они разные? Я думал это что-то общее для всех ОС и языков

просто термин очень широкий, можно поконкретнее?

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

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

так а эта очередь куда-то пишется?

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

несколько функций в один конвеер? Это разве не UFCS?

это другая тема, сначала разберёмся с сабжевыми пайпами

в простом случае пайп - соединение stdout одного процесса с stdin другого: grep -i “error” ./log | wc -l мы отдали всё, что нашёл греп в wc, чем посчитали количество ошибок

запустятся процессы grep и wc одновременно, нигде не будет хранится вывод грепа. просто по мере того, как он находит ошибку он отдаёт её в счётчик и забывает

https://habrahabr.ru/post/195152/

подробнее

а очередь эта в оперативку кладется?

да, но очень быстро чистится, поэтому по факту обычно пустая

кстати стандартный File блокирующий же?

да

асинхронных вещей в std нет пока

а как бы неблокирующий std выглядел?

как vibe.d

хотя не, наоборот, как vibe.d без файберов и тасков

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

спутал... на уровне системы есть кэш дисковый же

ERROR: S client not available

Олег, я не совсем понимаю как File может вообще неблокирующим. Типа файл может писать два потока? Или один пишет, а другой читает?

в этом контексте "блокирующий вызов" это тот, завершения которого нужно дожидаться, а потом уже следующий код будет выполнен

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

блокирующее чтение из файла: res = file.read(...); someFunc(res); // у нас уже есть строка неблокирующее чтение: file.read(function (res){ someFunc(res); }); // здесь ещё нет строки, res будет только в колбеке

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

поэтому делается так как как указал Grigirii

неблокирующий — обработка данных внутри функции получающей их так?

исполнение не блокируется на время чтения

потому что чтение делегируется на другой поток?

на системный в данном случае

нет, пототка не создаётся, но можно считать что это некий "системный поток"

просто как я понимаю легче всего это писать в языках где все функции — функции первого порядка т.е. типа js

D мало чем отличается в данном контексте

+

вот прям точно это хотел написать)

пока код ждет результата, планировщик на новый процесс перещелкивается?

ага

А если какой-то тяжелый рассчет нужно провести, то как оно работает? По факту же рассчет будет блокирующим

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

а вот где грань? Это все только опытным путем делается? типа "тут мы будем считать, значит лучше поток создать"?

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

да, именно так

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

А что почитать про организацию even loop ? Чтобы понять поглубже как оно работает

сложный вопрос. статьи по асинхронному программированию, исходники libasync

Напиши свой event loop =)

Самый простейший

документация к libev, libevent, libuv и тд

если хочется совсем до кишков, то select, потом epoll, kqueue

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

Напиши себе 3 функции которые последовательно печатают какие-нибудь цифры и добейся чтобы эти цифры печатались вразнобой из всех функций. Это и будет event loop

о