|
Игогошка!
1801 / 708 / 44
Регистрация: 19.08.2012
Сообщений: 1,367
|
|||||||
Ревью небольшого кода02.02.2016, 03:56. Показов 3095. Ответов 45
Метки нет (Все метки)
Хаскелл я изучаю совсем недавно, поэтому хотелось бы узнать, что и как можно было написать лучше.
Задача такая. Задается входной файл и длина маски. Во входном файле строки вида <бинарная маска> <значение>. Например, в файле одна строка "0*1* ADD". Нужно получить результат вида
0
|
|||||||
| 02.02.2016, 03:56 | |
|
Ответы с готовыми решениями:
45
Написал крестики-нолики. Сделайте ревью кода |
| 03.02.2016, 17:38 | |
|
0
|
|
|
306 / 101 / 18
Регистрация: 04.07.2014
Сообщений: 571
|
|||
| 03.02.2016, 17:45 | |||
|
Не по теме:
0
|
|||
|
Модератор
|
||
| 03.02.2016, 18:02 | ||
|
Смотрим время замены элемента в векторе - О(n+1). Смотрим время вставки элемента в Map - O(log n). Извлечение из вектора, конечно, быстрее. И, для вектора, можно сразу все элементы для одной маски вставить. Но, в начале, когда элементов ещё мало, Map выигрывает. А дальше, уже в зависимости от того, сколько неиспользуемых кодов останется. Считаем и думаем.
0
|
||
|
Игогошка!
1801 / 708 / 44
Регистрация: 19.08.2012
Сообщений: 1,367
|
||||||
| 03.02.2016, 19:34 [ТС] | ||||||
![]() Мутабельный вектор - Data.Vector.Mutable. У него не самый удобный интерфейс, нужно манипулировать с монадами. Его рассматриваем в крайнем случае. Иммутабельный вектор - Data.Vector. Все замечательно. У меня всего лишь tolist, replicate, //. Это O(n) - и лучше не получится сделать. Data.Map.Strict - O(nlogn). (кстати есть более интересный вариант Data.IntMap.Strict)
1
|
||||||
|
Модератор
|
||||||||||
| 03.02.2016, 20:03 | ||||||||||
|
Кликните здесь для просмотра всего текста
1
|
||||||||||
| 03.02.2016, 20:21 | |||
|
Не по теме:
Также придётся отказаться от представления данных процедурами их порождения, потому что хорошо работающие на запускаемой архитектуре алгоритмы эффективно работают именно на коробочках. Но это всё злые языки говорят... Я сам не проверял.
0
|
|||
|
Игогошка!
1801 / 708 / 44
Регистрация: 19.08.2012
Сообщений: 1,367
|
|
| 03.02.2016, 20:52 [ТС] | |
|
KolodeznyDiver,
Vector можно считать эффективной реализацией ассоциативного массива, если ключи являются числами и есть биекция между ними и целыми числами из множества 0..n-1 С insert я так и считал. n вставок по logn - итого nlogn для алгоритма. С вектором просто n. mporro, но сами структуры данных там самые обычные - computer science одна для всех.
0
|
|
|
Игогошка!
1801 / 708 / 44
Регистрация: 19.08.2012
Сообщений: 1,367
|
|||
| 03.02.2016, 22:04 [ТС] | |||
![]() log 1 + log 2 + log 3 + ... + log n = log (1*2*3*...*n) = log n! А вот http://stackoverflow.com/quest... roximation доказательство того, что O(log n!) и O(n log n) одно и то же. Я же не вставляю по одному элементу, у меня одна bulk операция. Она O(m + n) = O(n + n) = O(n)
0
|
|||
|
Модератор
|
|||
| 03.02.2016, 22:34 | |||
|
log 1 + log 2 + log 3 + ... + log n = log n + log n + log n + ... + log n
0
|
|||
|
Игогошка!
1801 / 708 / 44
Регистрация: 19.08.2012
Сообщений: 1,367
|
|||
| 03.02.2016, 22:46 [ТС] | |||
|
0
|
|||
|
Игогошка!
1801 / 708 / 44
Регистрация: 19.08.2012
Сообщений: 1,367
|
||||
| 03.02.2016, 23:27 [ТС] | ||||
|
Добавлено через 1 минуту Добавлено через 2 минуты А вот еще кстати: https://en.wikipedia.org/wiki/Big_O_notation Находим параграф Orders of common functions. Смотрим: O(nlogn) = O(logn!)
0
|
||||
|
Модератор
|
|||
| 04.02.2016, 01:04 | |||
|
Не по теме: Не исключено, что я чего то не понимаю, по этому пойду спать. :) Добавлено через 1 час 25 минут Не по теме: Уснёшь тут, когда всякие асимптоты в голове прыгают ... О(), они, да, справедливы в пределах. Но суть то в чём. Допустим, длина маски 8, вариантов 256. Для Map, первые элементы вставляются очень быстро, потому что всех данных словаря мало. А для вектора, он сразу размером в 256. И каждая замена его элемента выполняется копированием всего вектора (он же не мутабельный). Особенно будет заметна разница (в пользу Map), если " INVALID"-ов останется много и Map даже в конце его заполнения окажется небольшим. Вы же спрашивали
0
|
|||
| 04.02.2016, 06:40 | ||
|
Не по теме:
Кликните здесь для просмотра всего текста
STM ... разве его гдето нету?
0
|
||
|
Игогошка!
1801 / 708 / 44
Регистрация: 19.08.2012
Сообщений: 1,367
|
|||||||||||||
| 04.02.2016, 15:30 [ТС] | |||||||||||||
![]() В списках не вижу пока проблемы. У меня только операции либо доступа к голове списка, либо прохода по всем элементам. Вот может рассмотреть замену String на Data.ByteString.Char8?
0
|
|||||||||||||
|
Модератор
|
||
| 04.02.2016, 16:53 | ||
|
А "по взрослому" - большие последовательности данных (возможно бесконечные) conduit-ами или пайпами. Ну, я так, к примеру. В этом разделе примеры есть. И, кстати, по какой книжке(ам) Вы Haskell учили?
0
|
||
|
Игогошка!
1801 / 708 / 44
Регистрация: 19.08.2012
Сообщений: 1,367
|
||
| 04.02.2016, 19:00 [ТС] | ||
|
Прогнал себя через этот курс: http://www.cis.upenn.edu/~cis1... tures.html Начал читать Симона Марлоу, почти дочитал про монаду Eval (дошел до распараллеливания k-средних). Иногда заглядываю в What I Wish I Knew When Learning Haskell. Сейчас, когда я дошел до монадных трансформеров, я решил устаканить свои знания, налегая на практику. Вот пробую понаписать чего-нибудь и получить обратную связь.
1
|
||
|
Игогошка!
1801 / 708 / 44
Регистрация: 19.08.2012
Сообщений: 1,367
|
||||||
| 10.02.2016, 19:24 [ТС] | ||||||
|
Немного переписал:
0
|
||||||
|
Модератор
|
||||||
| 10.02.2016, 23:39 | ||||||
|
Изменения "просто так"
1
|
||||||
| 10.02.2016, 23:39 | |
|
Перевод небольшого кода из C# в C++ Оптимизация небольшого кода
Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Программное добавление префикса в нумерацию документов
Maks 27.10.2026
Реализация из решения ниже выполнена в самописной конфигурации на БСП (помощь начинающему коллеге).
Задача:
Программно добавить префикс в нумерацию документов.
Решение:
В модуле объекта. . .
|
После закрытия оутлука продолжает висеть процесс в диспетчере задач
Maks 27.10.2026
С недавнего времени в продакшене возникла проблема: при закрытии оутлука в диспетчере задач продолжал висеть процесс outlook. exe. Проблема возникла после установки MS Office 2021 LTSC на машинах, под. . .
|
Baragoz - DPS/HPS бот для WoW 3.3.5a, многоязычный
AmbA 26.10.2026
Хотите ещё ботов? У меня есть один! А я пока отдохну от него.
https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=12062&stc=1&d=1793007952
Инструкция внутри.
https:/ / youtu. be/ VpfFZSUDGnQ. . .
|
Особенности gif сгенерированных в Си
russiannick 21.10.2026
Рассмотрим генерацию gif файлов, которые в Си имеют свои особенности.
Gif представляет собой графический формат популярный в интернете. Посмотрим на палитру. Gif файл сгенерированный в си отличается. . .
|
|
FPS контроллер с анимированными Y-Bot и 3D-звуком miniaudio (Box3D, Recast, BehaviorTree.CPP, ozz-animation, ImGui, OpenGL и SDL3)
8Observer8 18.10.2026
Содержание блога | English Version
Полное мультиплатформенное руководство по стартовому проекту с FPS-контроллером игрока, анимированными роботами Y-Bot с 4-слойным блендингом, 3D-физикой Box3D,. . .
|
Локальный http сервер
Argus19 17.10.2026
Локальный http сервер
На работе, на двух локальных компьютерах круглосуточно работают программы опроса приборов с записью в книги Excel,которые раз в сутки записываются на сервер компании. Т. к. . . .
|
Копировать Windows на новый диск на UEFI
damix 17.10.2026
https:/ / uriesk. wordpress. com/ 2016/ 11/ 01/ move-window-10-to-ssd-on-a-uefi-dualboot-system-with-basic-linux-tools/
TL DR
Вставляем диск, а старый подключаем через переходник, грузимся с лайва. . .
|
ИИ не может найти нужный язык в списке
Supersumestria 05.10.2026
Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык.
Возвращает он вот это:
https:/ / i. **********/ vqBWLe2. png
Нужную строчку в 3й колонке просто выдумал. .
Это. . .
|