mayton2019

Парадокс Зенона?

Задача выглядит как поиск кратчайшего пути в графе. Но решать в географических координатах
сложно т.к. надо учитывать кривизну планеты Земля. На эту тему есть куча формул и еще лучше,
куча систем координат и API.

Но я-бы просил автора нарисовать на картинке как это он себе видит. Возможно тут либо все очень
проще. Либо очень сложнее.

Можно попробовать на Prolog написать. Правила (rules) известны. А в качестве утверждений - просто
проверить что существуют ли целые числа которые удовлетворяют всем rules.

В унарном виде - это как цепочка единичек. Например число 5 будет.

_11111_

Справа и слева должен стоять blank sysmbol. Типа признак конца ленты чтоб было что проверять.

Тогда (5 mod 2) = 1

И мы должны получить на ленточке просто единичку.

_1_

Это можно сделать поглощая пары соседних единичек. А для четного числа будет пустая лента. Тоесть остаток от деления равен нулю.

Ну вот такой алгоритм. Дальше надо делать конечный автомат который ищет пары единичек.

Есть массив [1,2,3,3,4].
Нет. Нет. Все не так. Бинарное дерево строится на основе любых произвольных массивов.
Не обязательно сортированных. То что ты привел это какой-то частный случай чтоб облегчить себе
жизнь. И непонятно зачем мы здесь будем обсуждать частный случай.

Вот попробуй построить дерево из
[5,1,3,2,4].

Семантические графовые базы данных скорее всего подходят под данную задачу. Типа RDF/Semantic Web.
В качестве языка запросов там могут быть использованы SparQL. В качестве платформы хранения.... а чорт
его знает. Там много форматов. И XML и JSON и есть бинарники и JDBC адаптеры.

Это вообще серебрянная пуля которая везде подходит. Даже реляционки можно также представить. Со своими
накладыми но можно.

Но есть несколько мыслей почему их применение может быть неудобным. Первая. Например - знания о том
как все внутри устроено - будут только у 1 человека. У создателя этой базы. И никто кроме автора
в этой базе ничего не найдет.

Вторая. В эпоху умных чятов такие базы знаний умерли очень быстро. Вернее сказать их полезность
сильно девальвировала. В 20м веке в такие базы много вкладывали. Делали ставку на то что системы
со строгими правилами позволят выводить новые правила и факты. Но не сбылось.

Возможно я ошибаюсь и автору нужно на самом деле другое? Что другое? Ну просто какой-то язык
разметки типа markdown language или вообще confluence где можно макросами расширить функционал
и просто делать ссылки на формулы. И может быть это автору будет достаточно.

Вобщем для более глубокого понимания хотелось-бы чтоб автор просто привел парочки примеров. Может
там реально все проще.

Например, есть двухмерный массив:

Сразу неправильно. В компьютерной графике и графическом моделировании (книжка образца 1990х годов)
перечислены большинство графических оптимизаций. И практически везде нет никаких много-мерных
массивов. Забудьте многомерные массивы если хотите перформанса. Это блажь. Забудьте пиксели-объекты. Никаких объектов! Только WORD (ARGB) или индесные цвета.

Тезисно.
1) Растровая картинка - всегда отображатеся в 1-мерный массив в памяти. Выравнивается по границе кеш-линии и т.д. Тоесть решил рисовать в 1024х768 в RGB цвете - будь добр выдели - 3145728 байт памяти (я округлил RGB до 4 байтов).

2) Все операции рисования линий, прямоугольников кругов и полигонов и даже шрифтов - работают через прямой (direct) доступ к памяти. Никто пикселями не рисует. И ежу понятно что накладные расходы на стек и все съедают и когерентность доступа идет всегда неудачно по кешам. Одни промахи. Эти-же принципы реализованы в OpenGL, Direct3d только там еще и с позиции параллелизма. Одну фигурку может рисовать несколько графических ядер.

Я не знаю как в Python. Здесь надо быть глубоким специалистом в Python чтоб понять как там соптимизировать for. (Я думаю никак). Но все быстрые графические алгоритмы обычно пишуться на C/C++ и там работают с бегущим указателем. Если условия позволяют - делают SIMD. Чтоб за 1 команду закрасить или наложить маску на 2 пиксела сразу. Или на 4. Или на 8.

Вообще с Питоном идея - тухляк изначально. Если хочешь быстро красить краской прямоугольники в экране - тебя надо реализовать это на сях а потом дописать фасад для Питона чтоб делать вызов сразу рисования прямоугольника. И все современные библиотеки машинного обучения вобщем-то так и реализованы. Питон - только запускает а реализация вращает циклы в других более быстрых языках.

Непонятно зачем автор протегал это АЛГОРИТМАМИ. Тут вобщем-то имеет место обычная работа с формочкой.
Дизайнеры форм лабают это и не зная ваших умных абстракций. Просто пишут там хендлер на каждую радио-кнопку или на чек-боксик и в зависимости от действий - скрывают некоторые филды или подсвечивают.

Но если вам интересна теория, то такое поведение можно описать небольшим конечным автоматом. Или
в данной задаче несколькими конечными автоматами которые взаимосвязаны по реакции на переходы.

Гуглить можно по FSM (Finite State Machine) и библиотек по сям и питонам будет много.

Вообще данная задача еще не набрала критическую массу знаний чтоб кодить ее в автоматах.
Время потраченное на библиотеки и на привязку их к формам может быть слишком большим
и эффекта не будет. Будет разочарование.

Какого размера у тебя массивы? Там для маленьких - вообще теоретическая формула не работает.
Видимо в силу когерентности кеша тупые и жлобские алгоритмы работают лучше чем умные и сложные.

Я думаю что теоретическая оценка начинает играть роль тогда, когда массив реально в несколько крат
превышает хотя-бы кеш L3.

Я для мелких массивов (2,3 элемента) сортировка пузырем вполне себе делает минимум операций.
Ее даже можно хардкодить размоткой циклов.

Есть также вопросы на собеседовании для джунов (Java) которые практически позволяют нагнуть новичка
показав ему на практике что вставка примитива в ArrayList (массив) работает быстрее чем вставка в LinkedList.

Опять-же этот эффект заметен на малых размерах массивов.

Поскольку случай - очень простой, то он решается шаблоном. Но если вместо а или б может быть
тоже выражение - тогда нужно определять свою грамматику. Например:
min ( min(a,b) , min (c,d) )
Тогда умные дядьки-теоретики берут язык описания грамматик. EBNF типа. И пытаются
свой новояз описать в терминах например EBNF https://en.wikipedia.org/wiki/Extended_Backus%E2%8...
Описывают что такое число. Какое оно. Отрицательное? Вещественное? Экспоентциальное?
Короче надо описать вообще все что может быть. Описывают функцию минимума.
Потом по этой грамматике создают парсер. Программно. И парсер на выходе выдает
дерево. Где корень - это вся грамматика а на листиках будут висеть числа. Или терминалки не помню
как они это называют. И вот когда ты уже получил это чортово дерево - можно ПРИСТУПАТЬ ко второй
части задачи - а именно к транформации в инфиксную форму. Но ты сначала реализуй хотя-бы первую
часть.

Это все теория и она требует погружения. Я думаю что эта задача и ей подобные в частных случаях
решаются проще. Если например твой язык поддерживает регулярки - то перечисли макс. число
вариантов что будут на входе и выбери через матчинг подходящий. Это - быстрее.

Насчет корней не знаю. Есть алгоритм Snowball https://snowballstem.org/demo.html#Russian
Он делает примерно то что нужно. Например сводит облако-облак. Сводит разные слова к основе.
А то что не смог свести ты можешь попробовать сам дописать в справочник или добавить свои суффиксы.

И у него есть несколько готовых реализаций на C#/Java. Я думаю что кто-то уже делал реализацию для PHP.

Напоминает попытку построить свой кеш. А зачем топик тегирован Ассемблером? Какая тут нерешаемая
для ассемблера задача?

Алгоритмы и структуры данных тесно связаны с зубо-дробительными бенчмарками. Как-то отсортировать терабайтный текстовый файл или найти два одинаковых числа в файле из чисел тоже большого размера.
Иногда такие задачи задают на собеседованиях Google и Microsoft.

И если вы будете изучать эти алгоритмы на js, то вы не сможете продемонстрировать эффективность этих
алгоритмов. Python машина - просто медленная. У нее конечно есть надстройки например над векторной
алгеброй которые позволяют быстро считать рутину вроде циклов над векторами. Но является ли это
программированием Python - чорт его знает. Как по мне - нет. Тут - другая экспертиза нужна.

В структурах данных важно также оценивать память "на глазок".

В этом смысла кодер С++ имеет много преимуществ т.к. он видит и понимает как распределяется память
в узле бинарного дерева например (два указателя по 64 бита + какой-то размер для ключа который тоже
можно посчитать). Какой аллокатор брать? Встроенный в язык new или нужно делать собственный.
Такой расчет важен для оценки например - применима ли структура данных вообще?
Какой толк от дерева если оно не влезет в оперативную память? А падение памяти в swap - тут-же замедляет
алгоритм в разы.

JS и Python не предоставляют тонкого контроля над памятью. У них своя модель построенная для комфорта
самого процесса разработки а вовсе не для струткуры данных.

Давайте порассуждаем что такое вообще "поворот дерева". Это - метафора. Это изменение двух потомков двух узлов a и b. По сути это функция transform:
void transform(Node *a, Node *b) {....}
при этом (a,b) - состоят в отношении relatives. Родственники.

Далее можно детализовать левый и правый поворот но сигнатура - таже самая. Звучит вопрос - можем ли мы сбалансировать дерево без использования такого шаблона разработки?

Тебе нужна функция цветовой дистанции между двумя цветами. Типа

double getDistance(int rgb1, int rgb2) {
    ....
}

Формула будет похожа на взвешенную сумму цвета как ты писал выше. Только в цветах
нужны будут разности r1 - r2 e.t.c. И взять декартово расстояние.

Она будет возрващать от 0 до некоторого максимального вещественного. Если 0 - то цвета идентичны.

Задаешь порог чувствительности например 5% и если цвета rgb1 и rgb2 близки - то соотв. считаешь
что совпадение было. Сравнивать по знаку == цвета нельзя в фотографиях. Там очень редко
бывает численное совпадение. Практически - никогда не бывает.