LINUX.ORG.RU

24
Всего сообщений: 212

Алгоритм автоматического размещения элементов диаграммы на сцене (только DAG)

знаю что проблема геморная, но может вдруг за последние годы чтото изменилось и появилось чтонить простенькое для частных случаев

нужен именно алгоритм, ибо придется встраивать в свою приложуху редактирования графов. ну или разве что есть чтото готовое на жс, будь он неладен

у меня конкретный граничный случай - направленный ацикличный граф, горизонтально ориентированный (входы слева, выходы справа)


наткнулся кстать на старую тему
Алгоритм автоматического размещения элементов диаграммы на сцене


https://yed.yworks.com/support/manual/layout.html
списочек впечатляет, хз что из этого взять, придется тыкать по очереди


p.s.
лол, а я сейчас понял что мегапрог ведь с этой траблой пополной столкнется (если к тому времени не пропадет) и наверняка скажет что это все от текстовых языков и на графическом он такое сделает за пару минут

 , ,

genryRar ()

Парсинг потока на пакеты сообщений - минимизировать копирование

Есть TCP соединение (т.е. поток байтов), из него эти байты читаются и разбиваются на сообщения-пакеты определённого протокола уровня приложения. Каждое сообщение имеет либо фиксированный заранее известный размер, либо в заголовке содержит длину. Максимальный размер пакета - N, заранее известен и ограничен.

Варианты реализации: 1) Пишем байты из сокета в буфер размером N, когда в буфере оказывается целое сообщение, вызываем функцию-обработчик этого сообщения. Недостатки - нужно целое сообщение в буфере. Допустим, в буфер пришло сообщение размером N/2, за ним сообщение размером N, но оно уже в буфер целиком не влазит. Поэтому, после обработки первого сообщения затираем его и перемещаем первый кусок следующего сообщения к началу буфера, используя memmove(). Затем читаем из сокета до победного конца. Мне здесь не нравится наличие memmove()

 
|----message1---||---mesage2-- 
0                            N

2) Выделяем буфер размером 2N. Читаем из сокета не больше N байт за раз. Если буфер заполняется на N или больше, читаем из сокета ровно столько, чтобы прочитать хвост последнего сообщения, размер хвоста известен из уже пришедшего заголовка. После этого пишем в буфер с начала. Здесь мне не нравится то, что recv() возможно придётся дёргать чаще мелкими порциями. Но вариант кажется оптимальным.

|----message1---||---mesage2----------|---------------
0                             N                      2N

3) Допускаем, что функции-обработчику не нужно целое сообщение в буфере, функция может хранить состояние и парсить сообщение по кусочкам, по мере прихода. Здесь недостаток в том, что поля сообщения придётся по байтам или по кусочкам копировать в отдельные буфера. Потому что в буфере чтения оно может не быть представлено в целом виде. В первых двух вариантах можно просто передавать указатели на поля внутри буфера чтения.

Что анонимный разум имеет сказать по этому поводу? Есть идеи|алгоритмы получше?

 , , , ,

Harald ()

Алгоритм делающие плавные замены между кадрами.

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

 ,

steemandlinux ()

задача на распределение ресурсов

Такая задача. Есть некая фабрика и есть время, за которое надо потребить сколько-то (Х) ресурсов. В каждый определенный промежуток этого времени фабрика может потребить только ровно Х_i ресурсов.

Поставщиков ресурса несколько. У каждого поставщика цена ресурса варьируется (дискретно) с течением времени. Фабрика может не только потреблять ресурсы, но и складировать (т.е. потреблять ресурс с избытком), чтобы в следующий раз вместо того, что брать ресурсы у одного из поставщиков - брать их со своего склада. Размер склада ограничен.

Собственно, цель - минимизировать цену закупки ресурсов за указанное время с учетом выполнения фабрикой плана потребления ресурсов.

Это задача решается методами исследования операций (симплекс метод) или я не в том направлении смотрю?

 ,

jcdr ()

Максимально быстрое сравнение чисел

Тяжело сформулировать, но я попробую.

1. Есть поток входных сигналов, чисел.

2. Числа с этого потока должны сравниваться с неким заданным значением (пускай одним).

3. Поток дискретный, пускай частота дискретизации 2 мс (каждые 2 мс на вход поступает новое значение).

4. Как максимально быстро произвести сравнение, как лучше всего сортировать числа на входе. Количество операций, выполняемых за такт известно, как и частота процессора.

5. Язык на котором это можно реализовать значения не имеет, если на каком-то быстрее, чем на других, то это тоже учитывать надо.

Где почитать на эту тему так, что б ответ был готов к концу дня. Или, может, вопрос банальный и ответ есть готовый.

 , ,

ivlu ()

Чтобы почитать из годной литературы по динамическому программированию?

Типичные задачи, алгоритмы, с примерами решений

 ,

next_time ()

Как построить Гамильтонов путь в матрице?

Привет. Задача выглядит примерно вот как: есть матрица, состоящая из 0, 1, а так же содержит одну 2. 0 - это свободная ячейка. 1 - это блок 2 - это начальная точка. Начиная с начальной точки, построить путь, который обходит все свободные ячейки по одному разу, не затрагивая блоки. Ну типа Гамильтонов путь. Ходить можно вверх/вниз/вправо/влево.

Максимальный размер матрицы 13х13 примерно, желательно чтобы алгоритм работал за разумное время.

Перемещено leave из general

 , , ,

nazzalexx ()

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

Как определить программно, что изображение имеет ли размытие или не точности при текущем масштабе просмотра?

 

victor79 ()

Тут есть кто прошарен в матрицах?

А вдруг внезапно препод по линалу? Нужно помочь решить задачу. Объяснить алгоритм.

 ,

Lizhen ()

Алгоритмы шифрования. Почему не смешать несколько?

В каждом мессенджере используется какой-то свой алгоритм, но почему-бы не сделать несколько, чтоб безопасность возросла? По принципу луковицы, в несколько слоев разными алгоритмами, збс же будет?

 , , , ,

floksy ()

Time-frequency analysis techniques

Спрошу и на лоре, почему бы и нет? Так вот, вопрос простой, нет ли у кого инфы по поводу алгоритмов выполнения Wigner-Ville distibution и Hilbert-Huang transform? Интересует как само существование готовых решений, так и инфа о скорости их выполнения. Рад буду подробным ответам, но пойдет и простое задание направления «куда копать».

 ,

ivlu ()

Какую книжку по алгоритмам стоит купить?

Сейчас начал читать переводное издание книги Скиены «Алгоритмы. Руководство по разработке». Написано доступно и есть каталог алгоритмов. Хочется иметь её в бумаге, но не могу найти где купить.

Какую книгу по алгоритмам, из продающихся в бумаге, стоит купить?

На амазоне даже со скидкой эта книга дороговато выходит ~3700р без доставки. Мне бы в пределах 2000р.

 , ,

the_real_kinik ()

Книжка по алгоритмам с задачами для школьников

Была такая pdf'ка по алгоритмам для школьников из какой-то школы с математическим уклоном, там задачи в основном, очень известная, никак не могу её нагуглить. Может кто-то понимает, о чём идёт речь?

 ,

grimwaken ()

Визуальное отображение прямоугольных сущностей на плоскости (поле «в клеточку»)

Привет специалистам LOR-а!

Имеется задача - поле «в клеточку» заполнено цифрами, при этом количество клеток много больше уникального количества цифр. По факту эти цифры - идентификаторы сущностей, которые «располагаются» на плоскости. Сущности только прямоугольные и, например, какая-то занимает 4 клетки:

.  .  .  .  .  .
.  1  1  .  .  .
.  1  1  .  .  .
.  .  .  .  .  .
.  .  .  .  .  .

Какая-то одну или две:

.  .  .  .  .  .
.  1  1  .  .  .
.  1  1  .  2  2
.  .  .  .  2  2
.  3  .  .  .  .

Теперь хочется как-то отрисовать это визуально, но возникают случаи вида:

.  .    .    .    .    .
.  .    .    .    .    .
.  223  223  224  224  .
.  223  223  .    .    .
.  .    .    .    .    .

Т.е. рядом дву сущности - 224 и 223, и их ID «похожи». Визуально трудно различить.

В результате возникает проблема: каким образом создать алгоритм перехода от целочисленного ID к строковому так, чтобы строчки максимально отличались друг от друга визуально? P.S. Готового критерия степени «визуального» отличия у меня, разумеется, нет, помимо очевидно факта, что 221 больше отличается от 223, чем, например, от «А0».

 

omegatype ()

Быстрый настраиваемый парсер обратных польских нотаций с биниднгами для питона?

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

 , ,

genryRar ()

GSM: Линия занята

Почему не сделали выход из dead-lock, когда абонент A звонит абоненту B, и наоборот: A>B && B>A?

 , ,

Mirage1_ ()

Мультиуровневый bsearch, нужно ли?

Мои исходные данные – массив структур с географической информацией:

struct Geo {
  std::string airport;  // level: 1
  std::string city;     // level: 2
  std::string province; // level: 3
  std::string nation;   // level: 4
  std::uint8_t subarea; // level: 5 | values: 11, 12, 13, 14, 21, 22, 23, 31, 32, 33, 34
  std::uint8_t area;    // level: 6 | values: 1, 2, 3
};

Надо много (и желательно быстро) отвечать на запрос «принадлежит ли Needle к Haystack». Где Needle всегда более специфично нежели Haystack, например:

belongsTo(Needle=City{Munich}, Haystack=Subarea{21}) -> true

Я думаю посортировать данные иерархически:

std::vector<Geo> geos = allGeos();
std::sort(geos.begin(), geos.end(), 
  [](const Geo& lhs, const Geo& rhs) {
    int areaCmp = lhs.area - rhs.area;
    if (areaCmp != 0)
      return areaCmp < 0;

    int subareaCmp = lhs.subarea - rhs.subarea;
    if (subareaCmp != 0)
      return subareaCmp < 0;

    int countryCmp = lhs.nation.compare(rhs.nation);
    if (countryCmp != 0)
      return countryCmp < 0;

    int provinceCmp = lhs.province.compare(rhs.province);
    if (provinceCmp != 0)
      return provinceCmp < 0;

    int cityCmp = lhs.city.compare(rhs.city);
    if (cityCmp != 0)
      return cityCmp < 0;

    return lhs.airport.compare(rhs.airport) < 0;
  }
);

И потом использовать bsearch() по партициям типа Needle на пути от Haystack. Т.е (псевдокод):

int level = levelOf(Haystack);
std::vector stack{ Range{geos.begin(), geos.end()} };

while (!stack.empty()) {
  Range partition = stack.back();
  if (partition.empty()) {
    stack.pop_back();
    ++level;
  }

  // depth-first
  if (level > levelOf(Needle)) {
    iterator begin = partition.begin();
    iterator end = lower_bound(begin, partition.end(), valueOf(*begin, level));
    stack.push(Range{begin, end})
    level -= 1;
    continue;
  }

  // level == levelOf(Needle)
  if (bsearch(partition, Needle))
    return true;

  // trim parent's begin()
  stack.pop_back();
  stack.back().begin() = partition.end();
  ++level;
}

Где level обозначает поле из Geo, соответсвенно комментарию.

Вопрос такой: может есть алгоритм (или структура данных) лучше подходящая под цель?

 ,

KennyMinigun ()

Программка для радио

Есть радио программа-плеер которая вещает на сервак, суть в том что нужна программа которая возьмет из определенной директории(их там много) и за рандомит песни и есть вставки из другой директории с болтавней все это в mp3, но есть условия

9:00-10:00 - music
10:00-(dependent from file) болтовня обычная
(dependent from file)-11:30 - music
11:30-(dependent from file) болтовня
(dependent from file)-12:00 - music
сам файл в формате m3u8
#EXTM3U
#EXTINF:12,джингл1
C:\Users\User\Desktop\РАДИО\джингл1.mp3
#EXTINF:438,Relaxea - Sunshine Delight
Z:\Автоматизация\музыка для радио\Chillout after work\After Work Chillout\001_Relaxea_-_Sunshine_Delight.mp3
#EXTINF:222,Minka - Little Cat
Z:\Автоматизация\музыка для радио\Chillout after work\After Work Chillout\002_Minka_-_Little_Cat.mp3
#EXTINF:962,Богданова
Z:\Радио\Рубрика Наперекор судьбе\Богданова.mp3//болтавня
........
нужно по длительности определить и подобрать и желательно чтобы разная была при каждом запуске также есть джингл 12 секундный который можно вставлять по несколько раз есть не хватает например минуты, P.S. вот желательно бы знать на каком языке это сделать и функции рекурсивно обходящие все поддиректории с добавлением всех файлов и определении их длин
Алгоритм такой:
1.Добавляем в вектора всю музыку и во второй болтавню(рекурсивно обходя директории и их поддиректории)
2.Открываем файл fopen(playlist.m3u8,"w");
Вставляем строку fwrite("#EXTM3U@);
Какой-то функцией определяем длину которая тоже в векторе еще одном будет, либо вектор состоящий из 
struct
{
std::string filename;
float length;
}
3 Подбираем длины чтобы был час по длительности с рандомом по выборке
4. Пишем 
frite("#EXTINF:"+vector[i].length.toString()+","+vector[i].filename);
frite(vector[i].filename);
5. Вставляем из вектора с болтавней одну композицию
frite("#EXTINF:"+vectortalk[i].length.toString()+","+vectortalk[i].filename);
frite(vectortalk[i].filename);
6.Повторяем предыдущие шаги с подборкой длин по расписанию
Well done!

 ,

Gremlin_ ()

Подскажите название метода объединения и разделения на группы?

Подскажите название метода, я его придумал, но на самом деле наверняка такой уже есть, просто все читать не перечитать.

Есть множество значений N, которые нужно поделить на группы. Значения между собой связаны, каждое значение привязано к другим M значениям. Чем больше у значения связей к другим - тем это значение более весомо, и больше вероятности что оно будет центром. Кроме наличия связей, сами значения ничем другим не различаются, и связи все не типизированны - просто связь.

Значениям назначаются статусы - либо является центром, либо притяными к центру.

Центрами становятся значения, которые не имеют между собой общей связи. Если между двух значений, которые ранее были центрами, появляется связь (связи могут добавляться и удаляться в процессе, так же как и сами значения), то тот из центров, который более весомый, поглащает менее весомый, и все ранее притянутые к поглощенному центру притягиваются к новому, если с новым у тех была связь. Если не было, то оставшиеся притягиваются к другим, либо оразуют собственный центр, если это наилучший вариант.

 

victor79 ()

Отзыв о книге «Алгоритмы на C++» Роберта Сэджвика

Ну, господа, получил-таки я книгу. Если честно, думал, что она будет поменьше, пхах. Касательно печати - вроде бы, ничего, пальцами тёр, не размазывалось, в отличие от дешёвых книжечек а-ля PocketBook. Корешок какой-то.. хлипенький, имхо, будто не здоровый талмуд сшивали, когда открываю-закрываю - поскрипывает. Хотя, наверное, слишком многого я хочу от современных издательств. Про содержание ничего сказать пока не могу, через месяца 4, может, через 5, отпишусь. Задавайте вопросы, если что недосказал.

https://postimg.cc/gallery/236vzeldm/

 , , ,

john_snake ()