Капля здравого смысла для Windows-разработки на C и C++

unordered_map тоже не идеален. Для интереса сравнил с гугловским dense_hash_map. Вставка 10 миллионов чисел, затем их же поиск. Результаты на стареньком ноутбуке с Core i5-3317U 1.7GHz:

unordered_set - 7.15 секунд

dense_hash_map - 1.75 секунды

Коварный план: почему всё вокруг ломается

У меня на ультрабуке Fujitsu тоже крепление петли ломалась. К счастью, больше ничего не повредилось. Починил суперклеем с содой.

Big O нотация в Swift

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

С учётом времени на сортировку будет время O(n*log(n)). Немного похуже, чем с хеш-таблицей, но гораздо быстрее, чем решение "в лоб".

Стресс-тестер для соревнований по программированию

Под Windows для аналогичной задачи использовал примерно такой bat-файл:

:again
  random_testgen.exe > input.txt
  solution_bruteforce.exe < input.txt > output1.txt
  solution_wrong_answer.exe < input.txt > output2.txt
  fc /W output1.txt output2.txt 
  if ERRORLEVEL 1 goto end
  goto again
:end

Удаление узлов из красно-чёрного дерева

Однко, декартово дерево попроще будет

Алгоритм Джонсона на орграфе с отрицательными дугами

На первой стадии алгоритма вместо обычного алгоритма Беллмана-Форда можно использовать его улучшенную версию под названием SPFA: Shortest Path Faster Algorithm.
Хотя в худшем случае (на специально подобранном графе) у него вычислительная сложность такая же, как у обычного Форда-Беллмана, но зато на случайных графах работает во много раз быстрее.
А пишется не сильно сложней: надо добавить очередь (как при поиске в ширину) и ещё булевский массив. В цикле берём очередную вершину из очереди и смотрим на смежные с ней. Если для какой-то из них оценку получается уменьшить, то кидаем вершину в очередь, но только если там её ещё нету (для быстрой проверки наличия в очереди как раз булевский массив и нужен).

Слияние списков на python. Сравнение скорости

Стоило бы тогда ещё сравнить функции sort() и sorted(). Я для интереса попробовал — разница заметная получилась:

list1 = [i for i in range(1, 200000, 3)]
list2 = [i for i in range(2, 250000, 4)]
%timeit res1 = sorted(list1 + list2)
%timeit res2 = list1 + list2; res2.sort()

6.73 ms ± 64.9 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
4.43 ms ± 38.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)