Смотрю делимость на 3 нечетных чисел. В дерево попадает 25. Но это не простое число делится на 5. И часто нужна балансировка, т.к. числа будут добавляться в возрастающем порядке, и дерево будет вырождаться в линейный список с максимальным временем поиска. М.б. сохранять несколько чисел в буфере, а потом добавлять в дерево случайнным образом?
На практике часто стоит задача оценки производительности (benchmark), и для нее часто используют РЭ в различных вариантах часто сознательно загружая ОЗУ.
Первая пришедшая в голову идея. Записываем, нпр., в дерево числа до 1 млн. начинаем удалять четные, удаляя каждую вершину дерева. Дерево уменьшилось вдвое, добавляем к дереву второй лимон чисел, продолжаем удалять четные. И т.д., пока дерво не достигнет лимита памяти. Запоминаем, то число, на котором встали с удалением кратных 2двум, обозначим его х2, Переходим к удалению троек (т.е. что делится на 3) в дереве нечетных чисел. Доходим до х2. Останавливаем удаление троек и запоминаем х3 = х2. Добавляем в дерево следующую порцию чисел, удаляем двойки, потом с х3 удаляем тройки. Аналогично с другими числами.
А тут еще вопрос, насколько поиск по бинарному дереву тормознее.
Я не спорю, тем более, что сам очень люблю использовать деревья (вообще графами занимаюсь :) Попробуйте реализовать этот поход в программе — тогда будет возможно количественное сравнение.
Как обычно: что нужно — на то и кидаем: нужно ускорить — не постоим за памятью, нужно комнату обогреть камень догрузить — подождем с обеда до обеда :) В вики, нпр., ссылки, где простоту каждого числа 1 битом кодируют…
Когда-то виртовский Паскаль и первые стандарты языка критиковали за то, что невозможно написать функцию умножения двух матриц в общем виде. Матрицы 5х5 — один тип, 6х6 — уже другой тип. Турбо Паскаль 3 и выше, и другие компиляторы имели расширения для обхода этой проблемы. Правда расширения не всегда удобные. Как в ФП решают эту проблему?
Это основа дизайна программ, предоставляющая связи между типами и законы (в математическом смысле, а не в инженерном) им присущие.
Не все матрицы можно умножать — размеры должны соответствовать. Можно в ФП задать такое правило на уровне типов?
Спасибо Вам и всем, кто помогает мне разобраться! :)
Со своей стороны, в первую очередь хочу отметить, что мне импонирует дружелюбная атмосфера, сложившаяся в данном обсуждении. До этой статьи я периодически читал про ФП, у меня постепенно накапливались недоуменные вопросы, которые откладывал «на потом». И вот этот «потом» настал, и за пару дней узнал больше, чем раньше за гораздо более длительный срок. Поэтому надеюсь, что и в дальнейшем обсуждении сообщество проявит терпение, отвечая на дальнейшие, может, не самые удобные вопросы — у меня их еще много)
Пользуясь случаем, предложу идею, м.б. кого заинтересует: тут много наговорили, отвечая на вопросы чайника в ФП (т.е. меня). Предполагаю, что я не оригинален, и что у других ФП-чайников есть похожие вопросы, но не все они будут читать это объемное обсуждение. Может, кто из экспертов-знатоков ФП переформатирует это обсуждение в FAQ и опубликует в виде статьи на Хабре? Уверен, что такая публикация будет очень актуальна.
Хотя в данный момент я далек от того, чтобы перейти на ФП, но вижу, что здесь очень интересная философия и практика, есть над чем подумать. В любом случае любому программисту очень полезно ознакомиться с общими принципами для расширения кругозора. Думаю, что если и не перейду на ФП, это довольно мимолетное знакомство повлияет на мой стиль написания программ.
Теперь позвольте задать очередную порцию вопросов.
для настоящей и осознанной типобезопасности
Не понимаю, как вывод типов повышает типобезопасность. В вики читаю:
опустить тип идентификатора в определении с инициализацией (см. синтаксический сахар). Например:
var s = «Hello, world!»; // Тип переменной s (от string) выведен из инициализатора
ИМХО действительно сахар.
Это не автодополнение IDE доступных полей и методов, а подсказка сложных и очень нетривиальных решений, которые потом могут превратиться в научные разработки.
Это не преувеличение? Как это можно превратить в научную разработку? Есть пример?
«Типо-ориентированное программирование»
Не нашел в гугле и вики внятных определений. Можно пояснение и ссылку?
Принципиальное отсутствие в многопоточности гонок, и проблем с общими ресурсами
К сожалению, не все задачи решаются такой схемой. Простейший ИМХО пример: 8 ферзей. На современных мощностях решается быстро возвратным алгоритмом, поэтому можем увеличить размерность.
М.б. нет, но из общих соображений многие молодые технологии бывают несовершенными. В любом случае выбор желателен: чем больше возможностей — тем лучше.
У вас и так уже кнопочки и GUI есть, значит, там заведомо есть что-то нечистое.
В этом я вижу проблему. Если функция
чистая_функция_очередное_приближение надолго задумывается, то в императивном языке вставлю в нее Application.ProcessMessages, чтобы нажатие кнопочки почувствовала. А в ФП моя функция перестанет быть чистой.
Т.е. переменные заменяются мемоизацией. Насколько это эффективно в плане времени исполнения? В сложных случаях можно опасаться, что компилятор не так поймет? И если не так, то сложно ли отловить такой баг?
Я про средства синхронизации внутри программы (всякие семафоры и т.д.)
Опишите какие проблемы вы тут видите.
Обычные проблемы синхронизации: гонки, общая область памяти для обмена данными между потоками, т.е. глобальные переменные и запоминание текущих состояний, и т.п.
Какого именно рода проблема? Дайте реальный пример.
Простейший пример: функция последовательными приближениями долго вычисляет результат, мне надоело ждать, нажал кнопочку, функция должна вернуть, что успела вычислить на этот момент.
видишь слово s — подставь определение из правой части.
«подставь» — это команда (что в программировании называется оператором). Для ее выполнения, надо не только подставить значение синуса, но и вычислить его сначала. Или тут только подстановка, как в препроцессорах? Но тогда синус будет вычислятся 2 раза, а не один.
Тут надо учитывать, что входными данными можно считать все действия пользователя, состояние файлов в файловой системе, данные в базе данных, даже генератор случайных чисел.
В результате получим проблемы по обработке событий в ходе вычислений. Еще один интересный вопрос: как при таком подходе возможна многопоточность? Мьютекс — это входные данные?
С одной стороны это создает кучу сложностей и ограничений. С другой убирает сайд-эффекты.
ИМХО в процедурном программировании сайд-эффекты убираются простыми ограничениями на глобальные переменные. Там это вопрос стиля. В ООП у каждого класса есть свойства и переменные, которые видны всем методам класса. Можно сказть, что там сайд-эффекты сознательно допустимы внутри класса и его потомков. И это бывает удобно. В ООП возможен плохой стиль, но ИМХО это не причина абстрактного ужаса перед сайд-эффектами. Не слишком ли их боятся?
комнату обогретькамень догрузить — подождем с обеда до обеда :) В вики, нпр., ссылки, где простоту каждого числа 1 битом кодируют…Не все матрицы можно умножать — размеры должны соответствовать. Можно в ФП задать такое правило на уровне типов?
Со своей стороны, в первую очередь хочу отметить, что мне импонирует дружелюбная атмосфера, сложившаяся в данном обсуждении. До этой статьи я периодически читал про ФП, у меня постепенно накапливались недоуменные вопросы, которые откладывал «на потом». И вот этот «потом» настал, и за пару дней узнал больше, чем раньше за гораздо более длительный срок. Поэтому надеюсь, что и в дальнейшем обсуждении сообщество проявит терпение, отвечая на дальнейшие, может, не самые удобные вопросы — у меня их еще много)
Пользуясь случаем, предложу идею, м.б. кого заинтересует: тут много наговорили, отвечая на вопросы чайника в ФП (т.е. меня). Предполагаю, что я не оригинален, и что у других ФП-чайников есть похожие вопросы, но не все они будут читать это объемное обсуждение. Может, кто из экспертов-знатоков ФП переформатирует это обсуждение в FAQ и опубликует в виде статьи на Хабре? Уверен, что такая публикация будет очень актуальна.
Хотя в данный момент я далек от того, чтобы перейти на ФП, но вижу, что здесь очень интересная философия и практика, есть над чем подумать. В любом случае любому программисту очень полезно ознакомиться с общими принципами для расширения кругозора. Думаю, что если и не перейду на ФП, это довольно мимолетное знакомство повлияет на мой стиль написания программ.
Теперь позвольте задать очередную порцию вопросов.
Не понимаю, как вывод типов повышает типобезопасность. В вики читаю:
ИМХО действительно сахар.
Это не преувеличение? Как это можно превратить в научную разработку? Есть пример?
Не нашел в гугле и вики внятных определений. Можно пояснение и ссылку?
За счет чего отсутствие?
чистая_функция_очередное_приближение надолго задумывается, то в императивном языке вставлю в нее Application.ProcessMessages, чтобы нажатие кнопочки почувствовала. А в ФП моя функция перестанет быть чистой.
Видимо технология еще слишком молодая для тотального использования.
Выше приводил пример.
Обычные проблемы синхронизации: гонки, общая область памяти для обмена данными между потоками, т.е. глобальные переменные и запоминание текущих состояний, и т.п.
Выше приводил пример: