Игогошка!
1801 / 708 / 44
Регистрация: 19.08.2012
Сообщений: 1,367
|
||||||
1 | ||||||
Ревью небольшого кода02.02.2016, 03:56. Показов 2069. Ответов 45
Метки нет (Все метки)
Хаскелл я изучаю совсем недавно, поэтому хотелось бы узнать, что и как можно было написать лучше.
Задача такая. Задается входной файл и длина маски. Во входном файле строки вида <бинарная маска> <значение>. Например, в файле одна строка "0*1* ADD". Нужно получить результат вида
0
|
02.02.2016, 03:56 | |
Ответы с готовыми решениями:
45
Проведите ревью кода? Прошу сделать ревью кода Написал крестики-нолики. Сделайте ревью кода Перевод небольшого кода из C# в C++ |
pycture
|
03.02.2016, 17:38
Ревью небольшого кода
#21
|
0
|
306 / 101 / 18
Регистрация: 04.07.2014
Сообщений: 571
|
|
03.02.2016, 17:45 | 22 |
Не могу судить, где понятнее. Возможно, если бы я, действительно, типы прописал, то стало бы яснее...
Не по теме: С одной стороны да... Но должны быть определённые гарантии со стороны компилятора. В половине случаев, в реальной ситуации, "на глаз", по исходному коду даже производительность Java нельзя оценить, а она императивная. А в Haskell и структуры данных другие... Боюсь, что если гнаться за предсказуемостью производительности, то код из функционального превратиться в процедурный...
0
|
Модератор
|
|
03.02.2016, 18:02 | 23 |
При чём тут хэш-таблица?
Смотрим время замены элемента в векторе - О(n+1). Смотрим время вставки элемента в Map - O(log n). Извлечение из вектора, конечно, быстрее. И, для вектора, можно сразу все элементы для одной маски вставить. Но, в начале, когда элементов ещё мало, Map выигрывает. А дальше, уже в зависимости от того, сколько неиспользуемых кодов останется. Считаем и думаем.
0
|
Игогошка!
1801 / 708 / 44
Регистрация: 19.08.2012
Сообщений: 1,367
|
|
03.02.2016, 19:34 [ТС] | 24 |
Вроде какие-то есть В каком смысле другие? А разве дело в этом? Я думал, что в дефолтной ленивости. При том, что это альтернативная реализация ассоциативного массива. Так, давай разберемся, а то я вижу, что мы запутались. Мутабельный вектор - Data.Vector.Mutable. У него не самый удобный интерфейс, нужно манипулировать с монадами. Его рассматриваем в крайнем случае. Иммутабельный вектор - Data.Vector. Все замечательно. У меня всего лишь tolist, replicate, //. Это O(n) - и лучше не получится сделать. Data.Map.Strict - O(nlogn). (кстати есть более интересный вариант Data.IntMap.Strict)
1
|
Модератор
|
||||||
03.02.2016, 20:03 | 25 | |||||
Vector - это именно непрерывный блок памяти. Ассоциативный массив - это Data.Array.
Вот Вам с Data.Vector.Mutable Кликните здесь для просмотра всего текста
1
|
mporro
|
03.02.2016, 20:21
#26
|
Не по теме: В том смысле, что естественным способом для Haskell представления данных является описание методов конструирования этих данных, а не хранения данных в коробочках. Я бы сказал так. Так дело именно в том, что для предсказуемости в производительности придётся отказываться от ленивости, потому что непонятно заранее ускорит ли это выполнение или замедлит. Ведь аппликативная редукция всегда завершается быстрее (если, конечно, вообще завершается)... Но вдруг мы сможем и не вычисляя отбросит аргумент? Я бы не стал на это делать ставки. Также придётся отказаться от представления данных процедурами их порождения, потому что хорошо работающие на запускаемой архитектуре алгоритмы эффективно работают именно на коробочках. Но это всё злые языки говорят... Я сам не проверял.
0
|
Игогошка!
1801 / 708 / 44
Регистрация: 19.08.2012
Сообщений: 1,367
|
|
03.02.2016, 20:52 [ТС] | 27 |
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 [ТС] | 29 |
Ну я немного упростил. Могу показать, что не неа, а ага
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 | 30 |
Конгениально! получается, что
log 1 + log 2 + log 3 + ... + log n = log n + log n + log n + ... + log n Я считал, что делалось бы у меня в коде, если заменить Map на Vector. У Вас, в СП, основная работа со списками (тормоза!), а вектор только для вставки неиспользованных значений, для этого он и не нужен.
0
|
Игогошка!
1801 / 708 / 44
Регистрация: 19.08.2012
Сообщений: 1,367
|
|
03.02.2016, 22:46 [ТС] | 31 |
Да, в асимптотике так и есть (то есть не забываем про О).
Где именно тормоза? А вектор нужен для вставки и сортировки. Это как раз львиная часть работы от всего. И он тут решает.
0
|
Игогошка!
1801 / 708 / 44
Регистрация: 19.08.2012
Сообщений: 1,367
|
|
03.02.2016, 23:27 [ТС] | 33 |
А где утверждается, что может?
Я поисследую этот вопрос. Добавлено через 1 минуту В смысле? При том https://ru.wikipedia.org/wiki/... 0%BE%D0%B5 Добавлено через 2 минуты А вот еще кстати: https://en.wikipedia.org/wiki/Big_O_notation Находим параграф Orders of common functions. Смотрим: O(nlogn) = O(logn!)
0
|
Модератор
|
|
04.02.2016, 01:04 | 34 |
Я про время выполнения при вполне конкретных, не ассимптотических n.
Не по теме: Не исключено, что я чего то не понимаю, по этому пойду спать. :) Добавлено через 1 час 25 минут Не по теме: Уснёшь тут, когда всякие асимптоты в голове прыгают ... О(), они, да, справедливы в пределах. Но суть то в чём. Допустим, длина маски 8, вариантов 256. Для Map, первые элементы вставляются очень быстро, потому что всех данных словаря мало. А для вектора, он сразу размером в 256. И каждая замена его элемента выполняется копированием всего вектора (он же не мутабельный). Особенно будет заметна разница (в пользу Map), если " INVALID"-ов останется много и Map даже в конце его заполнения окажется небольшим. Вы же спрашивали Вот, я и отвечаю, про данную программу - (свой первый вариант в этой теме).
0
|
pycture
|
04.02.2016, 06:40
#35
|
Не по теме:
Кликните здесь для просмотра всего текста
STM ... разве его гдето нету?
все познается в сравнении, грю же что конченым плюсистам вот такое должно быть гораздо ближе (для разнообразия) http://ideone.com/GwuQPy
0
|
Игогошка!
1801 / 708 / 44
Регистрация: 19.08.2012
Сообщений: 1,367
|
|||||||||||
04.02.2016, 15:30 [ТС] | 36 | ||||||||||
Я использую массовую замену. Это лишь одно копирование вектора.
Надо изменить
В списках не вижу пока проблемы. У меня только операции либо доступа к голове списка, либо прохода по всем элементам. Вот может рассмотреть замену String на Data.ByteString.Char8?
0
|
Модератор
|
|
04.02.2016, 16:53 | 37 |
Попробуйте, отчего же не попробовать? Если цель - самообучение, то попробуйте читать файл conduit-ом, к примеру. А то целиком файл в строку Вы и сами прочитали. Я "по сишному", с построчным чтением, изобразил.
А "по взрослому" - большие последовательности данных (возможно бесконечные) conduit-ами или пайпами. Ну, я так, к примеру. В этом разделе примеры есть. И, кстати, по какой книжке(ам) Вы Haskell учили?
0
|
Игогошка!
1801 / 708 / 44
Регистрация: 19.08.2012
Сообщений: 1,367
|
|
04.02.2016, 19:00 [ТС] | 38 |
Я прочитал Learn You a Haskell for Great Good! и читаю Haskell Programming from First Principles.
Прогнал себя через этот курс: 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 [ТС] | 39 | |||||
Немного переписал:
0
|
Модератор
|
||||||
10.02.2016, 23:39 | 40 | |||||
Изменения "просто так"
1
|
10.02.2016, 23:39 | |
10.02.2016, 23:39 | |
Помогаю со студенческими работами здесь
40
Оптимизация небольшого кода Разбор строчек небольшого кода Анализ небольшого кода по файлам Оптимизация небольшого кода, out of memory Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |