Задать вопрос
mayton2019

mayton2019

Bigdata Engineer
Ответы пользователя по тегу Алгоритмы

  • Что эффективней, чтение из файла или массив?

    mayton2019
    @mayton2019
    Bigdata Engineer
    Вопрос не глупый а вполне себе хороший.

    Его плавное развитие приводит к концепции баз данных. Самое главное что можно сказать тезисно это
    1) Пока памяти хватает (массив) - используй смело память
    2) Диск - больше и дешевле памяти
    3) С памятью работать легко. С диском - очень неудобно и надо обрабатывать IOExceptions почти всегда.
    Диски внезапно полны сюрпризов. Могут быть сетевыми дисками.
    4) Разные диски имеют скорость на порядки разную.
    5) Диски ведут себя очень плохо на random access. От этого даже метрика IOPS появилась.
    Ее очень любят обсуждать админы баз данных.
    6) Существуют структуры данных которые спецом создавались только для дисков (B+Tree)
    7) Диск - переживает выключение питания.
    8) Самые разумные решения - сочетают в себе и диск и память в тех частях кода где это нужно.
    9) Есть интерфейсы программирования которые виртуализирут диск как память. Этим пользуется
    SQLite например.
    10) Диск может достигать очень высокой последовательной скорости чтения или записи в файл
    при условии отсутствия конкурирующих записей в данный момент. Этим пользуются в БД
    для журналирования событий.

    В принципе если современный программист просто будет использовать только оперативную память
    то никто ему не сможет ударить по рукам или подойти с какой-то метрикой и чего-то там измерив
    сказать что он неправ. Тут уж только падения по OOM и потери информации и performance issues
    могут быть каким-то значимым аргументом.
    Ответ написан
    3 комментария
    3 комментария

  • Какую структуру данных выбрать для описания конфигуратора изделия?

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

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

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

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

  • Как быстро получить случайное слово из файла на 12 ГиБ?

    mayton2019
    @mayton2019
    Bigdata Engineer
    Какая максимальная длина слова? Ну допустим 20 символов.

    Не в курсе насчет питона. Но я-бы убрал фактор плавающей длины. Например я-бы разбил
    этот 12Гб файл на 20 файлов. Допустим в первом будут лежать все слова длиной в 1 символ.
    Во втором 2 символа. И так далее.

    Тогда формула будет такая. Считаем распределение слов по этим 20 файлам. Там гистограмма получается.
    Типа допустим 5% на 8 символьные слова. 8% на 9 символьные и так далее. Выбираем случайный файл
    ну как-бы учитывая "перекос". И потом уже внутри этого файла просто ищем случайное слово. Будет
    быстро потому-что слова уже имеют фиксированную длину.
    Ответ написан
    5 комментариев
    5 комментариев

  • Почему сортировка вставкой работает быстрее сортировки выбором в самом сложном случае?

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

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

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

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

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

  • Есть ли простое и быстрое решение определить, что фраза изменена незначительно?

    mayton2019
    @mayton2019
    Bigdata Engineer
    Можно вести подсчет триграмм. (Троек символов). И если разница в небольшом числе триграмм - тогда
    считаем что слова равны с "допуском". Величину допуска можно установить экспериментально исходя
    из тестовых выборок.

    Для случая сходразвал сход-развал.
    сходразвал: схо ход одр дра раз азв вал
    для слова с дефисом из триграмм выпадают
    одр дра
    следовательно допуск равен двум.

    Можно использовать би-граммы или четерех-граммы. Это вопрос эксперимента. Что лучше подойдет на
    данном наборе исходных данных.
    Ответ написан
    Комментировать
    Комментировать

  • Как превратить подстроку вида "min ( a, b )" в "a min b"?

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

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

  • Как находить исходное однокоренное слово без суффикса?

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

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

  • Как организовать массив состоящий из разных участков памяти?

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

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

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

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

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

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

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

  • Можно ли сбалансировать бинарное дерево поиска без использования поворотов дерева?

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

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

  • Что значит O(1)?

    mayton2019
    @mayton2019
    Bigdata Engineer
    Тут - проще объяснить применительно к конкретным языкам разработки и технологиями. Например время доступа к элементу хеш таблицы Java (HashMap) оценивается как O(1). Тоесть время всегда постоянное и не зависит от прочих условия типа размера таблицы. А если у нас вместо хеш-таблицы - красно-черное дерево (TreeMap) - то тогда время доступа оценивается как O(log n). Тоесть логарифмически зависит от размера данных в дереве.

    Считается что O(1) лучше чем O(log n). Но этот тезис действует на объеме данных близком к бесконечности. На малых объемах структуры - неразличимы или могут менять свои свойства в зависимости от разных начальных условий (были ли в кеше L1/L2/L3 до этого уже прочитанные данные).
    Ответ написан
    5 комментариев
    5 комментариев

  • Как выбрать объекты на изображении по цветам?

    mayton2019
    @mayton2019 Куратор тега Java
    Bigdata Engineer
    Тебе нужна функция цветовой дистанции между двумя цветами. Типа
    double getDistance(int rgb1, int rgb2) {
    ....
}

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

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

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

  • Как организовать алгоритм поиска по массиву ключевых слов?

    mayton2019
    @mayton2019
    Bigdata Engineer
    Тут наверное самый лучший алгоритм - это таблица.

    Но если есть энтузиазм - можно считать редакционное расстояние. Тогда столбец с Джонни не нужен.
    Ответ написан
    10 комментариев
    10 комментариев

  • Какой алгоритм быстрее и почему?

    mayton2019
    @mayton2019
    Bigdata Engineer
    Тебе не нужно сортировать все 10 000 000 элементов чтоб взять два минимальных. Достаточно одного прохода
    с отслеживанием двух наименьших {m1,m2} . И кейсов сравнений будет немного. Новый элемент больше - игнорируем. Новый элемент меньше обоих - вставляем в голову. Новый между ними - вставляем в центр.
    Ответ написан
    1 комментарий
    1 комментарий

  • Как поменять порядок битов в байте C?

    mayton2019
    @mayton2019
    Bigdata Engineer
    Тут все биты - перевернуты.
    На псевдокоде как-то так.
    int a = 0b0010_1101;
for(i in (1..8)) {
 b |= a & 0b0000_0001
 b <<= 1;
}
    Ответ написан
    2 комментария
    2 комментария

  • Как сформировать деревья в json используя golang?

    mayton2019
    @mayton2019
    Bigdata Engineer
    Я-бы предложил для начала уйти от этого странного способа описанию деревьев к инверсному списку
    По сути - добавить еще одну колонку которая указывает на родителя.

    id name     path  parent
-----------------------
1  Беларусь 1     null
2  Россия   2     null
3  Минск    1.3   1
4  Москва   2.4   2
5  СПБ      2.5   2
6  Невский  2.5.6 5


    Ну а дальше - select... connect prior и получим ранжированый курсор по дереву. Там-же будет
    доступно виртуальное поле level. И обходом этого курсора можно сделать JSON документ.
    Если level растет - то увеличиваем indentation и открываем вложенный элемент соотв.

    Если go-lang поддерживает stremable json writers то даже лучше.
    Ответ написан
    9 комментариев
    9 комментариев

  • Как генерировать тета-лабиринт?

    mayton2019
    @mayton2019
    Bigdata Engineer
    Здесь правда подходит любой алгоритм генерации лабиринтов с одним условием. Беря во внимание полярные координаты, ширина проходов в центральной части лабиринта должна быть примерно соизмерима с шириной проходов у края круга. Этого нельзя добиться просто заменив один прямоугольник на боковую поверхность цилиндра (бублика). Нужна коррекция. Корреция с учотом дистанции к центру этого бублика.

    Это мне кажется интересная часть задачи которую можно обсудить. Остальное - уже решено.
    Ответ написан
    2 комментария
    2 комментария

  • Два коня и праздник, что не так с кодом?

    mayton2019
    @mayton2019
    Bigdata Engineer
    Мне кажется шахматисты-теоретики давно расковыряли коня со всех сторон. DFS/BFS - это игра вслепую.
    А может быть есть некий сет стратегий которые ведут к победе. Например.
    - один конь делает нейтральные шаги туда-сюда.
    - второй конь целенаправленно двигается к этим двум шагам.
    - если промахнулся и не встретил - делает 3 или 5 тоже нейтральных шагов по кругу чтобы на нечетности поймать другого коня.

    UPD.
    Ответ написан
    36 комментариев
    36 комментариев

  • Какие есть курсы по алгоритмам с обратной связью или наставником?

    mayton2019
    @mayton2019
    Bigdata Engineer
    Я никогда не слышал чтоб кто-то читал чистые алгоритмы. Обычно программа более конкретная. Например алгоритмы игровой логики. Алгоритмы маш-обучения. Обобщенные алгоритмы какого-то языка (C++) etc.

    Чистые алгоритмы - это Кнут, Кормен. Короче сферическая лошадь в космосе.
    Ответ написан
    Комментировать
    Комментировать

  • Какой формулой можно вычислить смещение карточек от левого края до правого?

    mayton2019
    @mayton2019
    Bigdata Engineer
    Линейная зависимость. Бери некий box, который ограничиает карточки. Его размеры - это экран минус margins.
    И внутри этого бокса надо разложить карточки с одинаковым шагом. Беря во внимание что карточка тоже имеет
    размер - вычитаем ширину карточки из ширины бокса. Также с высотой. Оставшееся - делим на 4 и получаем шаг.
    Ответ написан
    12 комментариев
    12 комментариев