- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
/* a temporary boolean true value which changes the value of the referenced boolean variable to
true and to false on destruction, meant to be used for short-lived boolean changes*/
class tempTrue {
bool & bVal;
public:
tempTrue(bool & ref):bVal(ref){bVal = true;}
virtual ~tempTrue() { bVal = false; }
void toggle() { bVal = !bVal; }
};
class tempFalse {
bool & bVal;
public:
tempFalse(bool & ref):bVal(ref){bVal = false;}
virtual ~tempFalse() { bVal = true; }
void toggle() { bVal = !bVal; }
};
class tempToggle {
bool & bVal;
public:
tempToggle(bool & ref): bVal(ref){ bVal = !bVal;}
virtual ~tempToggle() { bVal = !bVal; }
};
class booleanInit {
public:
booleanInit(bool b):bVal(b) {}
operator bool & () { return bVal; }
operator const bool & () const { return bVal; }
private:
bool bVal;
};
class booleanTrue:public booleanInit {
public:
booleanTrue():booleanInit(true) {}
};
class booleanFalse:public booleanInit {
public:
booleanFalse():booleanInit(false) {}
};
Follow us!
но все равно слегка извратно.
Но ++ или push_back с такой схемой не прокатит :(
Что только не придумают, лишь бы не использовать персистентные структуры данных
так?
и deduction guide
Нет. Персистентные — это такие, с которых можно снимать снэпшоты практически бесплатно, потому что вставка элементов в них не изменяет структуру, а создаёт новую структуру, содержащую вставленный элемент.
См. Finger Tree, Ideal Hash Tree, etc.
Даже односвязный список без возможности модификации нодов является персистентной структурой данных: вставка в голову не меняет хвоста, можно шарить хвосты между несколькими списками. Сделать персистентную версию RBTree тоже довольно просто.
> std::stack<T> _d;
Да это же почти динамические переменные из common lisp. Десятое правило Гринспена в действии.
На самом деле, то, что хотел @Dummy00001 — транзакционная семантика в рамках блока. Т.е. есть внешняя переменная с committed data, и можно баловаться с локальной копией в рамках блока, но если не сделаешь "коммит транзации", локальная копия не запишется во внешнюю переменную.
Такое действительно очень удобно делать с персистентными структурами данных, особенно в многопоточных программах. Реализации этого механизма (STM) есть в haskell, clojure, scala (akka), и в плюсцы вроде тоже STM давно грозятся завезти.
Ахахах, мы раскрыли эксперимент по созданию искусственной чёрной дыры, ибо именно в неё сколлапсирует стандарт, если добавить в него семантику STM.
Она с императивщиной и побочными эффектами очень не дружит, скажем так. Как они это вообще себе представляют.
Пф, как обычно, напишут, что все непонятные ситуации являются UB. В той же кложуре в теории вроде тоже можно побочные эффекты в транзакцию притащить, только тогда ты ССЗБ.
unsafePerformIO тоже никуда не делся
{-# LANGUAGE Trustworthy #-}
... снэпшот может и бесплатный, но все остальные операции очевидно стремятся к как минимум O(N) (== копирование), в добавок с оверхедом выделения памяти и последующего GC. когда-то же копию придется удалять.
"[...] и в плюсцы вроде тоже STM давно грозятся завезти."
в STM все граблями обложено - потому что имитирует распределенную память, со всеми вытекающими. может для функциональщины (где все "теоретически" красиво) или жабы это имеет смысл, но для ц и крестов это (1) без граблей не прикрутиться и (2) будет тормозить по сравнению с какими классическими хэш локами (массив локов, lockarr[hashkey(нод).lock()/unlock()]).
"Сделать персистентную версию RBTree тоже довольно просто."
уже давно в почти всех версиях STL.
я по этим граблям ходил. классическое RBTree не персистентно, потому что там в референс коде, в одном/двух местах вместо смены нод местами, просто свопятся значения. фиксится относительно легко.
ЗЫ https://en.wikipedia.org/wiki/Software_transactional_memory#Implementa tions
Щито? Никому не сдались такие персистентные структуры, где O(N) вставка.
В большинстве случаев это либо O(log(N)), либо O(log(maxint)).
К примеру, в персистентном RB дереве нужно будет пересоздать путь от корня к ноду, не трогая поддеревья, что гарантированно O(log(N)) памяти и времени.
> уже давно в почти всех версиях STL.
Покажи хоть в одной.
я не правильно понял вот это:
"... потому что вставка элементов в них не изменяет структуру, а создаёт новую структуру, содержащую вставленный элемент."
я случайно подумал что опять ваша убогая функциональщина.
Я так понимаю, ты до сих пор не понимаешь. Ну да ладно.
> функциональщина
Так это и есть "функциональщина". Ты с гитом когда нибудь работал? Так вот, репозиторий гита — это по сути и есть одна большая персистентная структура данных. Файл ветки — эти указатель на текущую версию в графе.
Когда ты делаешь коммит — сюрприз — гит не делает копию каждого файла. При этом ты можешь прыгнуть в любую старую версию, как будто никаких последующих изменений и не было.
И git gc имеется, который недостижимые версии собирает.
Нет. Кончай пытаться функциональщину к здавому смыслу примазывать.
> Когда ты делаешь коммит — сюрприз — гит не делает копию каждого файла.
Естественно. Потому что репа, не смотря на все, это неразделимая структура: ты не можешь кусок гит репы взять, и на ней второй гит паралельно запустить.
А вот когда ты делаешь clone, что бы второй гит паралельно запускать можно было...
> Я так понимаю, ты до сих пор не понимаешь. Ну да ладно.
Да понял я это уже давно. И даже нечто подобное делал в прошлом с AVL деревьми и массивами для распределенной конфигурации. (Меняется конфиг, меняется дерево - новые/обновленные ноды другим сервакам посылаются, и там мерджатся в ихнюю локальную копию.)
Лол. В "функциональщине" никто структуры целиком не копирует, это бред. Именно потому, что модификации данных in-place нету, возможны персистентные структуры данных, которые примерно в 99.9% являются разного рода деревьями. На персистентных структурах данных вся "фукнциональщина" держится. Это как говорить "не надо привязывать массивы к программированию".
> Меняется конфиг, меняется дерево - новые/обновленные ноды другим сервакам посылаются, и там мерджатся в ихнюю локальную копию.
Не совсем понятно, зачем тебе там персистентные структуры данных, ну да ладно.
Ты так говоришь как если бы там были какие-то альтернативы. "Богатый" "выбор" структур данных, для "выразительного" "интутивного" программирования - для некоторых, отдельновзятых смыслов слов "богатый", "выбор", "выразительный" и "интуитивный".
> Не совсем понятно, зачем тебе там персистентные структуры данных, ну да ладно.
... Забавно. Я так понимаю, ты сам до сих пор не понимаешь. Ну да ладно.
Именно. На каждой стороне держишь полные снэпшоты + лог инкрементальных апдейтов, время от времени сбрасываешь новый снэпшот и транкейтишь лог.
Ok, можно считать дисковое представление таких деревьев персистентной структурой данных (иммутабельное дерево + список апдейтов к нему).
потому что иммутабельность никому ниразу в ж не сдалась. это не фича - это побочный эффект недоделаности функциональщины. во-первых. во вторых.
логи - а именно выбор времени когда их чистить - это геморой, грабли, и риск для интерактивности системы. если есть возможность - то лучше их вообще не заводить.
case in point: GC. тот же лог -
но только для "мертвой" памяти. (сколько нынче андроиду надо для комфортной работы памяти? слышал что 4GB это уже минимум. я планирую новый покупать с 6GB, потому что 2 очевидно мало.)
и если у тебя нормальный человеческий язык программирования - писаный людьми для людей - а не праффисарами-теоретиками для струдеров первокурсников - то лог в общем случае можно и не заводить, а делать все напрямую. дешевых и простых методов синхронизации в нормальных языках для этого хватает.
Так ты всю "конфигурацию" в памяти держал, а внезапное отключение питания решал хранением снэпшотов в /dev/null? Ты же толком так ничего не объяснил. Если ты считаешь, что от употребления слов "AVL дерево" и "обновлённые ноды" всё сразу встаёт на свои места, то ты ошибаешься. Особенно, учитывая твои предыдущие заявления.
> побочный эффект недоделаности функциональщины
Было бы интересней вести беседу, если бы с экрана не тёк твой антифункциональный баттхёрт.
> если у тебя нормальный человеческий язык программирования
Опять 25. От языка программирования ничего не зависит. Если ты что-то там не осилил, это твои проблемы, мне это не интересно.
Как ты организовываешь снэпшоты в распределённом хранилище от языка программирования зависит меньше всего.
лол. так а что там осиливать то? ты так про богатый выбор структур данных в выразительно-интуитивной функциональщине ничего и не ответил.
вот в этом то вся и херня. ц/кресты говно - спору нет. но и конкуренции им тоже нет по мощи структур данных. алгоритмы и программы - как ты не крутись - это все работа с данными.
если у языка база слабая - то и осиливать там нечего. у функциональщины база не просто слабая - она примитивная. (типа как m4 vs все остальные препроцессоры.) поэтому то концепция настолько привлекательна и могуча - и потому что реализовать может её любой детсадовец. поэтому её и любят. но поэтому то она и остаётся в лучшем случае нишей.
> Если ты считаешь, что от употребления слов "AVL дерево" и "обновлённые ноды" всё сразу встаёт на свои места, то ты ошибаешься.
Ты упомянул ранее что RBTree можно сделать персистентным - а я просто упомянул что то что ты говоришь, я уже делал, но с AVL. Да, можно. Все остальное - это детали реализации и конкретного приложения это структуры. Да, можно было сделать лог - но не нужен был. Было можно сделать дешёвые снэпшоты & CoW - но не были нужны. Изворотов с многопоточностью не было - локально использовали простой хэш reader/writer lock(ов).
А, то есть это был вопрос "какие чисто функциональные структуры данных существуют"? Так бы и сказал.
Ты, видимо, думаешь, что все пользуются исключительно списками, а массивы копируют целиком, когда нужно обновить значение.
Списки, понятное дело, прочно вшиты и (обычно) очень оптимизированы.
Быстрые мапы Int -> V
Самая популярная персистентная дека, отличная замена двусвязным спискам,
тот самый Finger Tree
Балансированные деревья
Персистентные массивы, основанные на Ideal Hash Tree — Из них же очевидным образом делаются персистентные хэш-таблицы.
Ну и понятное дело, если сильно хочется, можно временно срать в массивы, когда этого никто не увидит
> я уже делал, но с AVL
> сделать дешёвые снэпшоты & CoW - но не были нужны
Ты что-то не то тогда сделал. У тебя, похоже, какое-то O(N) копирование было.
99.9% уверен что все что ты запостил сделано на основе списков, или какими левыми хаками сделано.
потому что даже чтение описания (amortized running time + worst case performance) уже пахнет.
покажи подобный позор на каком ц или крестовом форуме - тебя там сразу камнями забрасают. на жабо-форумах просто за идиота посчитают...
теперь посмотри на это с другой перспективы: функциональные языки существуют 40+ лет - и из своего тупика до сих пор выкопатся не могут.
Ты даже не смотрел, откуда тебе знать, оракул. Я же тебя сказал уже, "в 99.9% являются разного рода деревьями"
> потому что даже чтение описания (amortized running time + worst case performance) уже пахнет.
> покажи подобный позор
Что ты несёшь? Какой amortized time вставки в конец вектора? А какой worst case? Что там у хэш-таблицы, самой лучшей структуры данных в мире? В чем заключается позор говорить о amortized/worst?
> функциональные языки
Что тебе языки всё покоя не дают? При чем они тут вообще? Это структуры данных и алгоритмы, они мало зависят от языка. На некоторых языках их более удобно реализовывать, на некоторые -- менее. Их в MIT на чуть более продвинутом курсе по алгоритмам читают
В том что во всех остальных языках у тебя там будет стоять твёрдое O(1) & O(log(n)). И за все десятилетия "развития" этой концепции, до этого тривиального уровня эти языки так и не дошли.
Хосподи, "правильный" язык делает структуры данных мягкими и шелковистыми, ага.
> твёрдое O(1) & O(log(n))
Кто-то прогуливал уроки.
Вставка в конец плюсового вектора:
amortized O(1), worst case O(N)
Лукап в хэш-таблице
expected O(1), worst case O(N)
Data.IntMap
> Many operations have a worst-case complexity of O(min(n,W)), W -- the number of bits in an Int (32 or 64).
Эффективно это O(1). Включая лукап, удаление и добавление элементов с произвольными целыми ключами.
У персистентных RB-деревьев в точности такая же ассимптотика, как у обычных -- гарантированное O(log(N)) на лукапы, вставки и удаления
Вектора из clojure тоже гарантируют вставку в конец и лукапы за эффективное O(1).
> до этого тривиального уровня эти языки так и не дошли.
Это ты после десятилетий своего развития не можешь отличить язык от структуры данных.
> Кто-то прогуливал уроки.
ты что идиот??? или ты просто крестов не знаешь?
> Вставка в конец плюсового вектора:
> amortized O(1), worst case O(N)
для чего существует двусвязный std::list - гарантированое O(1)
> Лукап в хэш-таблице
> expected O(1), worst case O(N)
std::map -> rbtree -> O(log(n))
так бы и сказал что ц/крестов не знаешь. я бы не ругался. ;-)
Лол, из какого моего утверждения это следует, знаток плюсов?
> для чего существует двусвязный std::list
Я тебе говорю, что есть персистентный вектор, у которого worst-case даже лучше, чем у std::vector, и при этом доступ в любое место практически за O(1), ты мне зачем-то тычешь список, у которого вообще семантика другая.
Ты утверждал, что нет нормальных персистентных контейнеров, я тебе говорю, что есть, практически на все случаи жизни.
> std::map -> rbtree -> O(log(n))
И что? Я что-то другое написал? Я тебе и говорю, что у персистентной мапы в точности такая же асимптотика, как у плюсовой эфемерной, и реализована она практически так же. Ты же повторяешь тоже самое и утверждаешь, что я не знаю плюсов. Л - Логика.
я утверждал что нет нормальных контйнеров в функциональных языках.
на что ты тыкнул в самую примитивную структуру в крестах - и сказал что функциональщина может лучше.
это что-то должно было доказать?
Щито? std::vector и std::unordered_map —
это самые важные, удобные и наиболее часто используемые контейнеры, причём не только в плюсах. Написать нормальный std::vector — это искусство, я бы даже сказал, что половину плюсовых фич в язык внедрили для того, чтобы нормальный вектор можно было написать. Написать нормальную хэш-таблицу ещё сложнее.
Я утверждал, что у этих контейнеров хреновый worst-case, и это мало кого волнует. И уж совсем непонятно, почему ты считаешь, что несовпадение amortized и worst case должно считаться "позором".
дам тебе пример из ц: ни одно серьёзное приложение не пользуется qsort(). догадайся почему. (у оракла в перформанс тьюнинг гайде, в факе, стоит даже это как вопрос, с ответом: нет, мы используем мердж сорт.)
Потому что сложность этой функции вообще не написана в сишном стандарте, как и то, что она должна быть реализована через quick sort?
std::sort часто используется, хоть там зачастую introsort, который вначале пробует quick sort, а маленькие куски сортирует insertion sort-ом.
Ничего плохого ни в quick sort, ни в векторе, нет, нужно просто правильно их использовать.
> у оракла
Скажи ещё, у них вектора и хэш-таблицы не используется, ага.
qsort != quick sortp
lol!
В вебките когда-то использовалось http://govnokod.ru/22815
Если порядок не нужен — использую unordered_map.
> это самые важные, удобные
> половину плюсовых фич в язык внедрили для того, чтобы нормальный вектор можно было написать
> Написать нормальный std::vector — это искусство
> Написать нормальную хэш-таблицу ещё сложнее.
Вот за такую хуйню у нас во дворе...
Кхм-кхм. Извиняюсь что вмешиваюсь в вашу высокоинтеллектуальную дискуссию, но выделенные мной фрагменты из сообщения roman-kashitsyn вызывают у меня сильные эмоции и кажутся мне полнейшей хуйней ерундой.
Скажем так, фичи плюсов абсолютно нахуй не нужны, чтобы написать вектор и анордеред мап. Я это могу и на ассемблере написать.
Никакого искусства в плюсовом векторе нет, это просто какая-то говнообертка над malloc/free со всякими там методами для проверки границ массивов, итераторами и прочим бредом. Кроме того, плюсовый вектор не умеет дергать realloc(), только malloc-memcpy-free. Также хотелось бы отметить, что стандарт плюсов выкинул поддержку CoW для вектора что довольно хреново.
Что же касается std::unordered_map (кроме того, что свою реализацию дерева(или хеш-таблицы) под unordered_map вполне по силам написать какому-нибудь студенту, так что никакого искусства тут нет) - так там оно не lock-free и построено на мютексах, что опять таки довольно хреново https://habrahabr.ru/post/251267/
Отсыпь мне этой травы... std::unordered_map вообще непотокобезопасный.
Тем более. Тогда в нем еще меньше искусства
Из std::unordered_map можно читать во сколько угодно потоков. А вот писать уже не получится, для этого туда надо мьютекс ставить http://stackoverflow.com/a/9685609
Вот если б сделали так, что и читать можно только в один поток...
Я не представляю, как можно запилить контейнер, который нельзя читать во сколько угодно потоков... Разве что мутабельный кэш какой-нибудь въебать...
- ахуеть, иди сходи за Нобелевской премией, осилившая регистрацию веб-макака.
"То есть заказчик говорить "не надо рекурсивно задать новые контракты для всех объект, от которого голова полностью функциональщины
Было бы интересно.
лол. так а что там нечего. у функциональщины. во-первых. во вторых.
логи - а именно в многопоточных программирования - писаный людьми для струдеров первокурсников - то лог в общем случае нишей.
> Если ты считаешь, что на каждый момент времени #вореции
(Ed: Тред не читай, сразу пиши.)
Обосрал тебя повторно, проверь.
> плюсов абсолютно нахуй не нужны
В том то и дело, что на сишке одноразовый вектор написать легко, но это будет не тот вектор. Он не будет интегрироваться с семантикой языка так, как std::vector.
> половину плюсовых фич в язык внедрили для того, чтобы нормальный вектор можно было написать
Шаблоны думаешь страуструп для чего придумал? Чтобы вы факториалы в компайл-тайме считали чтоли?
Шаблонные параметры шаблонов для чего впихнули? Внезапно, чтобы аллокаторы можно было параметром в контейнеры передавать, а не для того, чтобы Александреску было чем заняться.
Далее, для хорошей реализации нужна аккуратная работа с неинициализированной памятью, правильная семантика копирования и перемещения (к примеру, почему нельзя мувать контейнер, если конструктор перемещения элементов может кидать исключение?), strong exception guarantee и великое множество других деталей.
Если добавить small vector optimization и всякие игрища с константами, можно хоть целый месяц этот вектор писать.
Я согласен, что это в основном сложности самого языка, а не структуры данных как таковой. Но без хорошего знания тёмных уголков языка нормальный реюзабельный вектор не напишешь. Поэтому одноразовая "обёртка над malloc" — "не искусство", я такие на коленке много раз писал. А std::vector — "искусство".
> CoW для вектора что довольно хреново
CoW — вот где говно.
> unordered_map вполне по силам написать какому-нибудь студенту,
Одноразовую — сколько угодно, я студентом хэш-таблицы даже на фортране писал. Идея простая. Но хорошую униварсальную хэш-таблицу написать сложно.
Но у вектора таких нет.
Действительно. Я точно помню, что где-то видел
template <class T, template <typename> Alloc = std::allocator>... Видимо, всё же не для вектора.
Отрывок из интервью со степановым
The second significant new feature used in STL was template arguments which are templates themselves, and that's how allocators, as originally proposed, were done.
-- https://www.sgi.com/tech/stl/drdobbs-interview.html
Т.е. когда-то передавали шаблонный аллокатор параметром, но потом упростили.
Вектор это настолько примитивная по своей сути штука... Мне вообще кажется очень большой глупостью сама ИДЕЯ делать какие-то там контейнеры. В частности, я практически на 100% согласен со сказанным в http://www.stolyarov.info/guestbook#comment-606 так что не вижу смысла повторяться
> Шаблонные параметры шаблонов для чего впихнули? Внезапно, чтобы аллокаторы можно было параметром в контейнеры передавать
А чем их обычные сишные callback-и не устроили?
> CoW — вот где говно.
Почему б тогда CoW не выкинуть из линуксовых системных вызовов clone и fork, раз оно такое говно?
> Но хорошую униварсальную хэш-таблицу написать сложно.
Универсальную хэш-таблицу написать не сложно. Универсальную хэш-таблицу написать НЕВОЗМОЖНО. Например, она в плюсах уже неуниверсальна т.к. не thread-safe и ее только мьютексами обмазывать, или писать свою реализацию
Настоящий царь всегда может реализовать нужную ему структуру, попутно оптимизнув её под конкретный кейс?
собственно для чего и задумывалось
> stolyarov
Не позорился бы. Хотя он такой же кукаретик, как ты. В этом вы похожи конечно.
В нем нет поддержки realloc. Он не предназначен(не задумывался) для многопоточного чтения-записи в этот самый вектор (можно там теоретически что-то намудрить, чтоб например один тред мог читать/писать элементы вектора от 0 до 16, другой от 17 до 32 например, или чтободин читал-писал только четные, другой только нечетные, или еще ченить в этом роде. Кроме того, запретить схему с malloc-memcpy-free и использовать вместо этого brk/sbkr/mremap чтоб в случае необходимости расширить доступную вектора, не приходилось перемапливать все ебучие поинтеры на этот сраный вектор)
Может тебе надо сраный дек вместо ёбаного вектора? Раз на вставки в середину тебе наплевать и беспокоит только ресайз.
Я точно не помню, но там вроде даже поинтеры не плавают.
С linked list не придётся, если хранить указатель на ноду. В плюсах итератор списка как раз и является указателем на ноду.
пример реализации: https://wandbox.org/permlink/vrwfBc7NzxIcd33R
Байты, такты процессора - вот где мыслЯ, блеать, вот где красота и свежесть!
Dummy00001 - это злой нефункциональный (императивный?) Олег Сивоконь из злой параллельной вселенной
в тот момент, когда они они встретятся посередине (где-то в Молдавии, вероятно), произойдет аннигиляция с выбросом чудовищного количества тепловой энергии, что приведет к гибели человеческих жертв
... бедные жертвы. мало того что уже жертвы, так еще и гибнут.
> о. у тебя голова полностью функциональщиной отравлена.
Сказал человек, у которого голова полностью императивщиной отравлена. Сколько лет Вы императивщиной травитесь? Осознаёте, что она стала интуитивной из-за гигантского опыта?
Лично я теребонькать переменными начал ещё со школы, и теперь это для меня тоже интуитивно. Но если поговорить с нормальными людьми, они как минимум удивятся, что x в уравнении внезапно изменился, а порядок определений почему-то важен.
К тому же, до нас долгие годы вычисления (computations) проводились на бумаге. На бумаге нет присваивания, только иммутабельность и переопределение путём дописывания. Присваивание естественно только для табличек, покрытых воском.
> иммутабельность никому ниразу в ж не сдалась. это не фича - это побочный эффект
Вы так говорите, как будто программы либо сразу правильно писали, либо не отлаживали никогда.
Мутабельность глобальной переменной => функции зависят от хитрожопого состояния, хрен протестируешь.
Мутабельность какой-то хрени, на которую кто-то ссылается => надо думать о том, каким объектам нужно захватить конкретное состояние, каким нужно постоянно свежее; какие объекты в тапок насрут, если изменят по ссылке. Чтобы в наш объект не насрали, приходится его копировать и по сути городить аналог персистентной питушни.
Мутабельность - это когда значению по ссылке нельзя доверять и надо думать, кому и как его дать и где будет баг, если все полагались на константность, а теперь хочется изменить.
Пример: я пишу конфигурируемую питушню. Копировать ли мне конфигурацию себе? Хочу ли я смотреть её изменения?
JS/python: конфигурацию изменят и меня не спросят.
C++: мне передали const&, я не могу писать, а они снаружи издеваются и модифицируют.
Итог: я копирую конфигурацию в каждой функции, чтобы чего не вышло.
- ты ебанутый и не понимаешь семантику того, что пишешь?
Если хоть в одной вершине имеет смысл изменение/копирование, почти весь граф накрывается медным тазом мутабельности/неактуальных данных. То есть мне в каждый момент времени надо помнить весь этот граф, чтобы корректно обработать мутабельность.
Кто-то в цепочке тех, от кого я завишу, внезапно стал копировать объект, от которого он зависит - ко мне изменения не придут.
Кто-то в цепочке тех, от кого я завишу, внезапно стал изменять объект, от которого он зависит - ко мне станут приходить нежелательные изменения.
Размер семантики в моей голове - O(N). Чтобы меньше запоминать программисту (O(1)), надо либо оставить изменения и полностью запретить копирование (практически невозможно, т.к. любые производные параметры от наших данных будут по сути модицифированной копией, описать которую без копирования можно разве что реактивной питушнёй), либо запретить изменения и оставить иммутабельность.
Ромэн и Думми хотя бы делают вид, что по теме трындят, ты же вечно со своими ворециями.
Ну вот видишь? Сам всё понимаешь. И не стыдно тебе?
Сидит тут как сыч. И день и ночь. Вон, Ванька Ерохин уже, а ты всё сидишь.
Изучи основы алгоритмов и структур данных. Это, в общем, не лишние знания для программиста.
Основные тезисы:
1. Для O(f(n)) = O(k f(n)), существуют такие k, что f(n) != k f(n).
2. Из O(f(n)) > O(g(n)) не следует, что f(n) > g(n)
3. В реальной жизни действует не O(f(n)), а f(n)
3.1. Есть разница, программа работает 1 день или k дней.
3.2. Алгоритмы с более лучшей асимптотикой и большим влиянием младших порядков и констант на малых размерах данных могут вести себя хуже алгоритмов с асимптотикой получше.
Асимптотика рассказывает не про то, что "одна программа медленнее другой", а про то, "как быстро программа скатывается в говно с ростом N".
Вот и я пишу о том же. Поэтому асимптотика достаточным образом не описывает алгоритм.
Тогда прочитай уже определение O(N), сразу пропадёт желание дорисовывать константы внутрь скобочек...
> достаточным образом не описывает алгоритм
Для грубой прикидки в духе "если у меня станет в 10 раз больше комментов, то запрос начнёт обрабатываться в 100 раз дольше" - более чем достаточным. Алгоритм мог быть быстрым, мог быть медленным, но при увеличении N на порядок он скатывается в говно на джва. И константа здесь ни на что не влияет.
Я же не говорю, что константа влияет на O. И в моих утверждениях ничего такого не было.
Я говорю, что некорректно делать из асимптотики кумира и чморить тех, кто смотрит на мир чуть точнее, чем ты и видит не скупое асимптотическое O(N^2), а реальное N^2 + 1e6N + 1e9 и реальную задачу с N < 100.
* Там уже надо асимптотику при стремлении к нулю смотреть.
> при увеличении N на порядок он скатывается в говно на джва
Оно может и не увеличиться в конкретной задаче, и тогда асимптотические питухи будут лезть в сет из десяти элементов вместо поиска в массиве.
>> O(f(n)) = O(k f(n))
>> O(f(n)) > O(g(n))
> Что ты делаешь с моей математикой, прекрати...
Что-то не так? Может, с буквами не так, но по сути верно в реальной задаче.
Это реальное приближение настолько же грубое, насколько и асимптотическая оценка. За это и чморят тех, кто пытается строить из себя царя, а на деле считает в таких же абстрактных попугаях.
> в сет из десяти элементов вместо поиска в массиве
Раз уж у нас специальная олимпиада - сравнил линейный поиск в массиве из 10 интов (1.9 сек) с std::unordered_map (1.7 сек). На 5 элементах они сравнялись. Асимптотические питухи соснули.
Но если цари рассуждают так об алгоритмах в себе без уточнений, то да, жечь царей!
P.S. Кстати, в тех случаях, о которых я говорил, все алгоритмы над ограниченными данными переходят из O(f(N)) в O(1), т.к. N <= M, M - const и O-нотация становится бессмысленной.
А поскольку память у компов всегда конечна - все алгоритмы имеют сложность O(1).
Я чморю даунов, которые пишут значки, смысл которых не понимают. Таких как ты.
> O(f(n)) > O(g(n))
Что ты делаешь с моей математикой, прекрати...
При изменении условий контракты придётся изменить и пройтись по всему графу сущностей. То есть заказчик сказал "А", а мне надо рекурсивно задать новые контракты для всего графа и скорректировать код.
> разделением типов данных на value и reference.
Это же как раз целый граф. Или предлагаете тупо все неизменяемые данные по значению передавать, а все изменяемые - по ссылке? Если ставить ссылки на константы, описанная мной проблема вернётся.
Кстати, в вебе как раз эта питушня в самом начале и поднимается. Когда у тебя неявная типизация и просто x, а не type x или type& x, и ты не думаешь о типах, типы начинают думать о тебе и привлекать твоё внимание багами.
- ахуеть, иди сходи за Нобелевской премией, осилившая регистрацию веб-макака.
"То есть заказчик сказал "А", а мне надо рекурсивно задать новые контракты для всего графа и скорректировать код."
- я надеюсь, что ты сейчас стебёшь или гонишь, потому что это очень подозрительно, когда заказчика ебёт, принимает ли твой интерфейс let или var. Ну или ты никогда не видел живого заказчика
Только вот не надо завидовать.
> это очень подозрительно, когда заказчика ебёт, принимает ли твой интерфейс let или var
Я думал, на говнокодике люди поумнее сидят, но нет. Ведьм вэберов сжигают, думать отказываются.
Заказчик говорит "хочу вот такую настройку", и константа, общая для всех объектов некоторого типа, становится переменной со всеми вытекающими.
- я тоже думал, но тут попался ты.
"Заказчик говорит "хочу вот такую настройку", и константа, общая для всех объектов некоторого типа, становится переменной со всеми вытекающими"
- макака, давай какой-то пример из реальной жизни. Пока что всё выглядит так, что на каждый чих заказчика или начальства тебе нужно переписывать половину кода. Ты погромирование учил по книжке рецептов для мультиварки?
Я развлекался концепцией некоторое время.
Самое загадочное что языки которые не страдают проблемами - Lisp (и в какой-то степени Erlang) - почему то считаются плохими. А хаскель, от которого веет недоделаностью, почему на передовых.
Я забил на функциональщину просто потому что она зашла в тупик, сидит в этом тупике, и наслаждается этим отсутствием прогрэсса.
Уж извините что меня dead-ends не привлекают.
Даже каким brainfuck'ом мозги поразминать полезнее.
Замыкания, map/reduce уже добавили в языки. Чистые функции упрощают тестирование. Персистентные структуры данных помогут, когда зависимости в сложной системе и слежение за модификациями окончательно задолбают. Лучше меньше думать и сразу использовать иммутабельную питушню, которая в большей степени готова к расширению.
Чем больше я использую императивную питушню, тем больше уважаю ФП, где простой иммутабельностью пофиксили многие баги императивщины.
Ага, чтобы мутабельные части растащить друг от друга - рабочий каталог и файлики с указателями на ветки.
А вот папке objects с иммутабельными файлами конкурентный доступ ничего не сделает. Её можно было бы тупо симлинком цеплять к обоим гитам, и всё бы работало (ну кроме gc).
> я случайно подумал что опять ваша убогая функциональщина.
А оказалось, что линуксовый RCU list.
З.Ы. Не, сам RCU list всё-таки мутабельный. Только данные иммутабельные и копируются.
"Intel STM Compiler Prototype Edition implements STM for C/C++ directly in a compiler (the Intel Compiler) for Linux or Windows producing 32 or 64 bit code for Intel or AMD processors. Implements atomic keyword as well as providing ways to decorate (declspec) function definitions to control/authorize use in atomic sections. A substantial implementation in a compiler with the stated purpose to enable large scale experimentation in any size C/C++ program. Intel has made four research releases of this special experimental version of its product compiler."
"G++ 4.7 now supports STM for C/C++ directly in the compiler. The feature is still listed as "experimental", but may still provide the necessary functionality for testing."
линк: https://gcc.gnu.org/wiki/TransactionalMemory
если компилер сам это делает, тогда есть шанс большинство граблей обойти. за исключением нормальных граблей распределенки. но для десктопных приложений этом может быть и не критично. (для серверных скорее критично - но это все равно умирающая ниша, и там большинство все равно пользуются RDBMS которые в принципе это же и делают.)
ну-ка поясни (пожалуйста)
А плюсы раньше были популярнее, чем сейчас? Я вот и не знаю крупных "плюсовых" интернет-компаний кроме яндекса, гугла и вроде пейсбука. Раньше было больше?
Отставной шпрехшталмейстер, дядя Володя!
что, к слову, есть оригинальное поведение перла. что именно меня всегда c local и напрягало: после `local $a`, $a становится undef.
Perl очень хороший язык. Он же не виноват что он никому не нужен
Это дерьмо можно разгребать только сообща, цехом разгребателей, ибо один в нём попросту утонет. А для домашней разработки лучше всего - делфи.
Попробуйте продукты Embarcadero
Посетите сайт Embarcadero: https://www.embarcadero.com/ru/
• CBuilder https://www.embarcadero.com/ru/products/cbuilder
• Delphi https://www.embarcadero.com/ru/products/delphi
• RAD Studio https://www.embarcadero.com/ru/products/rad-studio
Бесплатные продукты:
• Delphi Starter https://www.embarcadero.com/ru/products/delphi/starter/promotional-download
> предлагает сибилдер
Си билдер не кресты
Стертор не программтст
Я всего-навсего тёмный, несведущий выходец из кишлака, который познал мощь и прелесть визуального программирования и который сейчас играет с продуктами Borland, радуясь тому, что у его формы нажимаются кнопочки.
Трамвай построить - это не ишака купить.