Russian Qt Forum
Ноябрь 23, 2024, 00:14 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Russian Qt Forum > Forum > Программирование > Алгоритмы > Структуры данных для поиска
Страниц: 1 [2]   Вниз
« предыдущая тема следующая тема »
  Печать  
Автор Тема: Структуры данных для поиска  (Прочитано 15773 раз)
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #15 : Апрель 07, 2012, 16:28 »
Цитата: QuAzI от Апрель 07, 2012,  15:49
..соответственно выравнивается по 4 байта и имеет вполне съедобную структуру, при прямом обращении к памяти скорость просто шикарна.
Цитата: V1KT0P от Апрель 07, 2012,  16:02
Тебе нужны LODы? Ну так сделай пару лодов, и выбирай их в зависимости от необходимой точности.
Спасибо конечно, но давайте не тратить время на обсуждение как упростить и/или изменить постановку задачи. Если бы такая возможность у меня была - я бы ее охотно использовал. Мне нужен (быстрый) поиск а не тупой перебор.

Память брать можно. Сейчас пиксель под 100 байт, может будет больше, ничего, переживу, это мои проблемы.
Записан
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2095



Просмотр профиля
« Ответ #16 : Апрель 07, 2012, 16:37 »
Цитировать
Теперь пробегаемся по всем пикселям, для каждого смотрим маркированных ближайших соседей. Допустим все они оказались одного (или близкого) цвета. Все хорошо, пошли дальше. Если нет - надо маркировать новый пиксель. Это изменит расклад как для последующих так и для предыдущих - теперь новая точка может оказаться ближайшей вместо старой.
1) По всем - это вообще по всем 10^6 или по маркерованным?
2)  для каждого смотрим маркированных ближайших соседей. В смысле?
3) Допустим все они оказались одного (или близкого) цвета. Кто они? Ближайшие маркированные соседи или просто ближайшие соседи?
4) Все хорошо, пошли дальше. Если нет - надо маркировать новый пиксель. Какой именно?
5) Это изменит расклад как для последующих так и для предыдущих - теперь новая точка может оказаться ближайшей вместо старой.  Этого я вообще не понимаю..

Какая то запутанная логика(

Можно на каком нить миниатюрном примере: Что вначале было и что в конце должно быть?
Записан
Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
V1KT0P
Гость
« Ответ #17 : Апрель 07, 2012, 16:45 »
Цитата: Igors от Апрель 07, 2012,  16:28
Спасибо конечно, но давайте не тратить время на обсуждение как упростить и/или изменить постановку задачи. Если бы такая возможность у меня была - я бы ее охотно использовал. Мне нужен (быстрый) поиск а не тупой перебор.
Пока подробнее какие именно пиксели надо искать не напишешь, врятли получишь ответ.
Это тоже самое что спросить какой лучше алгоритм сжатия использовать, не объяснив какие данные необходимо сжать. Может это текст(PPMD), звук(flac), бинарные файлы(upx) и т.д.
Записан
QuAzI
Гость
« Ответ #18 : Апрель 07, 2012, 16:47 »
По сабжу - ну будет там скучная собственная структурка, в которой будет три переменных: вертикаль, горизонталь, цвет пихеля. Дёшево и сердито. Никаких деревьев и прочих плясок с бубнами. И в итоге всё равно получается "тупой перебор". Выигрыша от "распоточить", не будет, там же не рассчёты, а тупой поиск в примерно одной области памяти, больше затраты будут на поддержку "многопоточности" и сохранение атомарности для списка, в который структурка пишется.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #19 : Апрель 07, 2012, 18:11 »
Псевдокод
Код
C++ (Qt)
bool ValidatePixel( const CPixel & target, const std::vector <CPixel *> & markedNeighbours )
 
Аргументы

- target - немаркированный пиксель подлежащий проверке
- markedNeighbours - вектор всех маркированных пикселей которые влияют на target (т.е. target лежит внутри круга захвата для каждого элемента вектора)

Возвращаемое значение: true если с target'ом "все хорошо" и баланс достигнут. Иначе false

Что значит "все хорошо"? Здесь уже используется масса вариантов, некоторые из них отпадут, новые добавятся. По существу это еще одна (другая) задача. Простейший пример: вычисляем средний цвет по всем markedNeighbours и сравниваем его с цветом target. Разница не превышает заданный порог - вернули true, иначе false. Наша тема - поиск, и с этой точки зрения нам важно только одно - изменился вектор источников - валидность пикселя возможно изменилась. Расчет закончен если для всех немаркированных пикселей ValidatePixel вернула true.
Записан
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2095



Просмотр профиля
« Ответ #20 : Апрель 07, 2012, 19:02 »
А в чём проблема то? Всё равно ж тогда по всем не маркированным пикселям нужно пробежаться.. 
Записан
Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #21 : Апрель 07, 2012, 19:17 »
Цитата: m_ax от Апрель 07, 2012,  19:02
А в чём проблема то? Всё равно ж тогда по всем не маркированным пикселям нужно пробежаться.. 
А проблемы такие

1) Пробегаясь для каждого немаркированного надо как-то собрать маркированных соседей

2) Это в первый раз по всем. Потом маркируя пиксель мы можем получить изменение расклада соседей в относительно небольшой окрестности и лупить по новой весь мульон раз за разом выглядит глупо.
Записан
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2095



Просмотр профиля
« Ответ #22 : Апрель 07, 2012, 19:51 »
Ну со вторым пунктом понятно.. Правда, не думаю, что здесь вы существенно выйграете в производительности, если учесть, что маркированных пикселей останется ничтожно малая часть от общего их числа.. Ну да ладно.

По первому пункту: не понятно, что значит: надо как то собрать маркированных соседей? 
Записан
Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #23 : Апрель 07, 2012, 19:55 »
Цитата: m_ax от Апрель 07, 2012,  19:51
По первому пункту: не понятно, что значит: надо как то собрать маркированных соседей? 
Ну тот вектор markedNeighbours (пост #19) надо же как-то получить, он ведь разный для каждого проверяемого
Записан
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2095



Просмотр профиля
« Ответ #24 : Апрель 07, 2012, 20:07 »
Цитировать
Ну тот вектор markedNeighbours (пост #19) надо же как-то получить, он ведь разный для каждого проверяемого
Ну так модифицируйте его при каждом проходе..  Непонимающий
Записан
Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
Tonal
Гость
« Ответ #25 : Апрель 09, 2012, 08:41 »
Вроде как напрашивается граф: к маркированной точке приделываем список ближайших маркированных точек с расстояниями.
Далее проверяем только их - обход графа в ширину.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #26 : Апрель 09, 2012, 09:07 »
А чего это мы так отчаянно (и неумело) велосипедим?  Может это... стоит открыть книжки?  Улыбающийся
Записан
Страниц: 1 [2]   Вверх
  Печать  
« предыдущая тема следующая тема »
 
Перейти в:  


Страница сгенерирована за 0.074 секунд. Запросов: 22.