Добрый вечер всем! В Рефале со списковой реализацией двоичный поиск с функцией first всё равно будет иметь сложность O(n), т.к. сама функция first имеет линейную сложность. Однако, число сравнений ключей будет меньше — O(log n), но сами сравнения сложнее, чем используя ассоциативный поиск (встроенное равенство vs вызов функции сравнения и анализ результата). Поэтому здесь выгоду от двоичного поиска нужно мерять на практике.
У меня был опыт оптимизации поиска в словаре при помощи хеширования. Нужно было искать среди нескольких тысяч имён, представленных как последовательности литер. Я стал вычислять хеш с остатком деления на какое-то простое число (37 кажется), имена сгруппировал в корзины по хешу. Поиск осуществлялся образцом вроде: s.Hash (e.Name) e.Buckets-B (s.Hash e.Names-B ((e.Name) e.Value) e.Names-E) e.Buckets-E Т.к. число корзин было сравнимо с корнем от типичного числа ключей, поиск получался не линейным, а O(√n) и это измеримо повысило производительность. С уважением, Александр Коновалов From: Стеллецкий Василий sw710_AT_yandex.ru <[email protected]> Sent: Sunday, November 10, 2024 6:27 PM To: [email protected] Subject: Re: Сфера применения Рефала - все Уважаемые господа! Долго сдерживался, но все же решил влить свою ненаучную струю в эту стройную концепцию ;) Тут недавно (уже почти 2 года назад) мой сын привлекал внука к программированию нормализации телефонных номеров... Они писали на Python. Я подумал, что это проще реализовать на рефале, и написал код... Оказалось, по размеру примерно одинаково. Всё равно все условия надо обрабатывать... Но далее он собирался эту функцию использовать в своей рабочей системе обработки базы данных. А как туда воткнуть функцию на рефале? А насколько это будет эффективно? Т.е. получается, что во-первых лучше писать на том языке, которым лучше владеешь, а во-вторых рефал проигрывает в коммуникации с другими языками и системами. Про словари... Может быть я еще живу в прошлом веке... Но мне кажется, что Нормальные словари должны быть внешними. Если словарь можно поместить в память рефал-машины - то это словарик. Кстати, если он отсортирован, по нему тоже возможен двоичный поиск с помощью машинной функции first, что на мой взгляд существенно уменьшает время доступа к информации. Мне в мою бытность в библиотеке приходилось программировать из рефала доступ к внешним текстовым словарям. Я использовал двоичный поиск по файлу и некий "кэш" в рефале размером 10000 звеньев (то же с двоичным поиском через first)... Время работы программ было вполне приемлемым. ... не знаю как продлить рефалу жизнь ... -- С уважением, Василий [email protected] <mailto:[email protected]> ---------------- 07.11.2024, 21:41, "Александр Гусев gusev_aleksandr_AT_mail.ru" <[email protected] <mailto:[email protected]> >: Кому: refal ([email protected] <mailto:[email protected]> ); Тема: Сфера применения Рефала; Такого рода соревнование уже было: 1. Аналоговые компьютеры против цифровых в 70-х. Цифровые были весьма несовершенны, но массовы. Аналоговые давали мгновенный результат и не имели проблем численных методов того времени. Но проиграли ввиду сильной зависимости от человеческого фактора. Всегда в наличии нужен был умный и знающий специфику программист. 2. Процессоры Intel （кирпич, поддерживающий архаичные команды) и Motorola (с ноготок и более качественным функционалом). В области компьютеров Motorola проиграла в нулевых к всеобщему изумлению поклонников Apple. Заявления о преимуществе в энергетической эффективности менее чем на порядок, а то и два, недостаточно для победы над уже массовой, увы, технологией нейросетей. Мне кажется, что интереснее объединение программной (Рефал) и стохастической (нейросети) технологий, использование сильных сторон каждой. Либо нужны какие-то оригинальные (или гениальные) маркетинговые ходы. Пока я вижу массовое желание использовать нейронки в программировании вместо людей. Даже если они выдадут некачественный, но работающий продукт, потребителя можно уговорить (или заставить) платить за него. И это будет катастрофа для тех, кто хочет быть программистом и работать головой, а не другими частями тела. Причём такой софт не сопровождается, а переписывается нейронной сетью весь каждый раз при внесении изменений. Через несколько лет квалификация людей упадёт и они перестанут делать code review таких инкубаторных систем. И где контроль за «железным братом»? Вот здесь как раз есть место Рефалу либо другим подобным способам обработки логики. Но чтобы сделать тут даже первые шаги, нужны готовые и проверенные решения. И люди, способные соединять одно с другим. -------- Пересылаемое сообщение -------- От кого: Mike Potanin mpotanin_AT_gmail.com <[email protected] <mailto:[email protected]> > Кому: [email protected] <mailto:[email protected]> Дата: Среда, 6 ноября 2024, 16:53 +03:00 Тема: Re: Сфера применения Рефала ... Хотя в лингвистике сейчас все захватили нейросети, мне кажется что для работы с текстами у классических методов есть шансы, скажем опередить нейросети по энергопотреблению и возможности анализа. Здесь интересно было бы генрировать программы анализа естественного языка и перевода с него на язык формальной логики с помощью машинного обучения (генетических алгоритмов, чего-то типа индуктивного логического программирования). С уважением, Александр Гусев [email protected] <mailto:[email protected]>
