При хостинг поддержке Интернет-сообщества VBIOS CS-Mapping.com.ua
Вернуться   CS-Mapping.com.ua > Forum > Разработка игр > Кодинг > Кодинг для Half-Life 1
Ник
Пароль
Регистрация Правила форума FAQ Пользователи Администрация Календарь Поиск За 24 часа Пометить все разделы прочитанными

Ответ
 
Опции темы Поиск в этой теме Опции просмотра
Старый 14.11.2018, 05:38  #21
DrTressi
DrTressi
Хрустик
Регистрация: 06.03.2010
Адрес: На белом свете
Возраст: 25
Сообщения: 6,300
Замечания: 16


По умолчанию

2 ncuxonaT: Ну хорошо, допустим. Тогда два вопроса:
1. Когда сортировать? При парсинге методом вставки или после квиксортом?

2. Что делать дальше с отсортированным массивом?
DrTressi вне форума Ответить с цитированием
Старый 14.11.2018, 07:21  #22
ncuxonaT
ncuxonaT
Майор
Регистрация: 05.05.2013
Сообщения: 1,068


По умолчанию

2 DrTressi: а какая вообще задача стоит? Просто посчитать уникальные вершины? Или прописать их в индексы треугольников?
ncuxonaT вне форума Ответить с цитированием
Старый 14.11.2018, 07:55  #23
DrTressi
DrTressi
Хрустик
Регистрация: 06.03.2010
Адрес: На белом свете
Возраст: 25
Сообщения: 6,300
Замечания: 16


По умолчанию

2 ncuxonaT: Просто посчитать уникальные вершины и вывести их на экран.

Прописывать их в индексы треугольников - это уже конвертация, и в этом случае, можно и подождать. А вот получение инфы о модельке должно происходить быстро.
DrTressi вне форума Ответить с цитированием
Старый 14.11.2018, 15:39  #24
ncuxonaT
ncuxonaT
Майор
Регистрация: 05.05.2013
Сообщения: 1,068


По умолчанию

2 DrTressi: если вставляешь в массив только уникальные вершины, то их количество равно длине массива.
Если вставляешь в массив все вершины с сортировкой в конце, то нужно пробежать по массиву и увеличивать счетчик, если текущая вершина отличается от предыдущей.
ncuxonaT вне форума Ответить с цитированием
Старый 14.11.2018, 20:13  #25
Дядя Миша
Дядя Миша
Регистрация: 28.03.2010
Адрес: Кубань
Сообщения: 14,502


По умолчанию

[ Цитата ] Кстати да, идея захешировать при загрузке мне тоже приходила, а потом сравнивать хеши
Хэш вертекса не влезет в 32битную переменную. Разве что ты ограничишь диапазон значений для всех трёх координат и то не факт. Обычно хэшируют по двум координатам, а третью уже находят обычным перебором.
[ Цитата ] поиск уникальных точек - около минуты.
У тебя контейнеры общего назначения плюс еще и цикл в цикле. Если развернуть - быстрее будет.
[ Цитата ] В отличие, например от OBJ, где просто массив уникальных точек изначально
Никто не запрещает в OBJ писать дубликаты. smd без индексации, это да.
[ Цитата ] Если уникальный вертекс меньше последнего элемента, проверенного двоичным поиском, то на его место
Так у меня вопрос не к функции сравнения, а к быстродействию Insert. Когда ты брутфорсом перебираешь, ты просто дописываешь новый вертекс в конец массива и это быстро. А когда ты при каждом новом унике сдвигаешь весь массив, это уже медленно. Как вообще в Делфи работа с массивами организована? Там какие-то встроенные средства языка?

Дядя Миша, подумав, добавил 14.11.2018 в 20:16
[ Цитата ] Когда сортировать? При парсинге методом вставки или после квиксортом?
Ты не сможешь сортировать "после", бинарный поиск работает только с отсортированным массивом.

Последний раз редактировалось Дядя Миша, 14.11.2018 в 20:16.
Дядя Миша вне форума Ответить с цитированием
Старый 14.11.2018, 22:27  #26
ncuxonaT
ncuxonaT
Майор
Регистрация: 05.05.2013
Сообщения: 1,068


По умолчанию

[ Цитата ] Так у меня вопрос не к функции сравнения, а к быстродействию Insert. Когда ты брутфорсом перебираешь, ты просто дописываешь новый вертекс в конец массива и это быстро. А когда ты при каждом новом унике сдвигаешь весь массив, это уже медленно. Как вообще в Делфи работа с массивами организована? Там какие-то встроенные средства языка?
Как везде, наверное. Динамические массивы. Когда меняешь длину, память перевыделяется, это не очень быстро. Для примера, при загрузке модели на полмиллиона уникальных вершин, если менять длину массива при добавлении каждой новой вершины - время работы около 1с. Если заранее задать большой массив - время работы около 0,8с.
Очевидно, сдвигать массив быстрее, чем перебирать каждый раз сотни тысяч элементов.
[ Цитата ] Ты не сможешь сортировать "после", бинарный поиск работает только с отсортированным массивом.
Если искать дубли перед вставкой, как я описывал выше, то сортировка будет получаться автоматически. А если сортировать большой массив со всеми вершинами, то бинарный поиск не нужен уже, все дубли будут друг за другом идти.

ncuxonaT, подумав, добавил 14.11.2018 в 22:49
Кек, переписал функции поиска и сравнения на использование указателей, теперь время работы 0,35с.

Последний раз редактировалось ncuxonaT, 14.11.2018 в 22:49.
ncuxonaT вне форума Ответить с цитированием
Старый 15.11.2018, 19:26  #27
Дядя Миша
Дядя Миша
Регистрация: 28.03.2010
Адрес: Кубань
Сообщения: 14,502


По умолчанию

[ Цитата ] Когда меняешь длину, память перевыделяется, это не очень быстро
Необязательно. Можно два массива сделать сразу и пинг-понгом гонять между ними.
[ Цитата ] Очевидно, сдвигать массив быстрее
Сдвигать тоже по разному можно, я ж почему и спросил, как в дельфи это реализовано.
[ Цитата ] Если искать дубли перед вставкой, как я описывал выше, то сортировка будет получаться автоматически
Так это единственный вариант по сути. Но я всё равно не поверю что у тебя сдвиг так быстро происходит. 500 тысяч раз сдвинуть даже 1-2-3 мегабайта и всё за 0.3 секунды. Оператива какая DDR5?
Дядя Миша вне форума Ответить с цитированием
Старый 15.11.2018, 23:06  #28
ncuxonaT
ncuxonaT
Майор
Регистрация: 05.05.2013
Сообщения: 1,068


По умолчанию

Ха, приколюха. Я так искал уникальные индексы в obj файле, но они там записаны в порядке возрастания. Поэтому сдвиг вообще ни разу не вызывался, каждый новый элемент записывался в конец массива всегда. Попробовал сделать в обратном порядке, чтобы всегда сдвигался весь массив. На той же модели время работы выходит 3 минуты, при этом сдвигается полтора терабайта.

Выходит, вариант с сортировкой полного массива без сдвигов будет практичнее. 3 миллиона вершин у меня считаются за 2 секунды. Пример кода:
Код:
var
  verts: array of TCoord;
  i: integer;
  dups: integer;

  procedure qSortVerts(l, r: integer);
  var
    i, j: integer;
    q, w: TCoord;
  begin
    i := l;
    j := r;
    q := verts[(l + r) div 2];
    repeat
      while verts[i] < q do
        Inc(i);
      while q < verts[j] do
        Dec(j);
      if i <= j then
      begin
        w := verts[i];
        verts[i] := verts[j];
        verts[j] := w;
        Inc(i);
        Dec(j);
      end;
    until (i > j);
    if (l < j) then
      qSortVerts(l, j);
    if (i < r) then
      qSortVerts(i, r);
  end;

begin
  setlength(verts, 3000000);

  for i := 0 to 2999999 do
    verts[i] := vec3(random(2000)-1000, random(2000)-1000, random(2000)-1000);

  qSortVerts(0, 2999999 );

  dups := 0;
  for i := 1 to 2999999 do
    if verts[i] = verts[i - 1] then
      Inc(dups);  
end;       
ncuxonaT вне форума Ответить с цитированием
Старый 15.11.2018, 23:43  #29
Дядя Миша
Дядя Миша
Регистрация: 28.03.2010
Адрес: Кубань
Сообщения: 14,502


По умолчанию

[ Цитата ] Поэтому сдвиг вообще ни разу не вызывался
Всмысле отсортированы? прямо в точности так, как ты их сортировал?
[ Цитата ] Выходит, вариант с сортировкой полного массива без сдвигов будет практичнее
Давай по пунктам, правильно ли я тебя понял.
Вот как себе это представляю я:
1. открываем SMD и начинаем его парсить
2. первый прочитанный вертекс добавляем в наш массив (можно сразу хапнать кусок мегабайт на пять, чтобы избежать мелких реаллокаций). Увеличиваем счётчик вертексов на еденичку.
3. Поскольку у нас массив уже имеет в себе какое-то содержимое, то при следующем добавлении вертекса применяем к нему твой бинарный поиск.
4. если вертекс не обнаружен, добавляем его, либо методом сдвига, либо через указатели, но через указатели стрёмно, а если через индексы, тебе вероятно придётся строить две таблицы индексов - туда и обратно. Поэтому для простоты считаем, что ты добавляешь вертексы в случайном порядке в середину массива либо сдвигом, либо пинг-понгом, копируя в соседний массив в цикле. Оба этих мероприятия достаточно затратные, ну ты уже сам убедился.
Вот так я себе это представляю. Но ты говоришь что решил задачку через qsort.
Каким образом? Если ты отсортировал ВЕСЬ массив, включая дубликаты, то бинарный поиск у тебя ожидаемо сфейлит, он не поддерживает дубликаты. Если ты отсортировал массив без дубликатов, то каким ты их отфильтровал, не прибегая к бинарному поиску?
Мне синтаксис дельфи режет глаза с непривычки, я сходу не пойму что в твоём коде происходит. Завтра постараюсь глянуть, у меня тут аврал наработи, даже вспачитать зайти толком не могу.
Дядя Миша вне форума Ответить с цитированием
Старый 16.11.2018, 00:05  #30
ncuxonaT
ncuxonaT
Майор
Регистрация: 05.05.2013
Сообщения: 1,068


По умолчанию

[ Цитата ] Всмысле отсортированы? прямо в точности так, как ты их сортировал?
Вроде того. Каждая новая уникальная вершина всегда "больше" предыдущих уникальных. Поэтому записывается в конец массива. Повезло, наверное.
[ Цитата ] Если ты отсортировал ВЕСЬ массив, включая дубликаты, то бинарный поиск у тебя ожидаемо сфейлит, он не поддерживает дубликаты.
Сортирую ВЕСЬ массив, но бинарный поиск не нужон уже. В отсортированном массиве дубликаты идут подряд. Я один раз прохожу по массиву и сравниваю каждый элемент с предыдущим. Если они равны, значит текущий элемент дубликат.
ncuxonaT вне форума Ответить с цитированием
Старый 16.11.2018, 19:30  #31
Дядя Миша
Дядя Миша
Регистрация: 28.03.2010
Адрес: Кубань
Сообщения: 14,502


По умолчанию

[ Цитата ] Сортирую ВЕСЬ массив, но бинарный поиск не нужон уже
И что прям qsort за 0.3 секунды сортирует массив на 500 тысяч вертексов?
qsort довольно тормозная штука, особенно стоковый.
Но тебе жеж мало только отсортировать. Тебе надо еще заполнить соседний массив где дубликатов не будет.
Дядя Миша вне форума Ответить с цитированием
Старый 16.11.2018, 19:49  #32
ncuxonaT
ncuxonaT
Майор
Регистрация: 05.05.2013
Сообщения: 1,068


По умолчанию

[ Цитата ] И что прям qsort за 0.3 секунды сортирует массив на 500 тысяч вертексов?
На 500 тысяч вертексов сортирует за 0.25 секунды.
[ Цитата ] qsort довольно тормозная штука, особенно стоковый.
Разве кусорт уже не самый быстрый метод сортировки? Вообще в лазарусе нет стокового кусорта. Я выше привел код, который использую.
[ Цитата ] Но тебе жеж мало только отсортировать. Тебе надо еще заполнить соседний массив где дубликатов не будет.
Точно так же пробежать один раз под отсортированному массиву и скопировать в новый массив каждый элемент, не равный предыдущему.
ncuxonaT вне форума Ответить с цитированием
Старый 16.11.2018, 21:12  #33
AHTu6uoTuK
AHTu6uoTuK
Лейтенант
Регистрация: 10.03.2012
Адрес: Москва
Возраст: 20
Сообщения: 760
Замечания: 2


По умолчанию

[ Цитата ] Разве кусорт уже не самый быстрый метод сортировки?
Вроде как не факт.
У кусорта в плохом случае можно получить сложность O(n^2), а у хипсорта всегда гарантируется O(n*log(n))
AHTu6uoTuK вне форума Ответить с цитированием
Старый 22.11.2018, 09:28  #34
nemyax
nemyax
Ф. А. Капица
Регистрация: 30.07.2015
Сообщения: 492


По умолчанию

[ Цитата ] Сообщение от ncuxonaT: Разве кусорт уже не самый быстрый метод сортировки?
Не во всех случаях жеж, хотя и во многих.
Пробовали набивать вершинами дерево, а потом его сплющивать в массив?
nemyax вне форума Ответить с цитированием
Ответ

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра

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

BB-коды Вкл.
[IMG] код Вкл.
HTML код Выкл.
Быстрый переход



Часовой пояс GMT +3, время: 12:01.


Designed by FT-502, TRUP@C. Originally by Ulric Spaak
Hosted by: VBIOS.COM, Powered by: vBulletin
copyright © 2002 - 2018 by CS-Mapping.com.ua Community