Один из способов улучшить производительность - это понять, что вам не нужно фактическое расстояние.Сравнение квадрата расстояния достаточно хорошо, поэтому вы можете пропустить вызов функции sqrt
.
Еще одна вещь, которая может, но не обязательно, ускорить процесс, - начать с вычисления только расстояния x.Используйте тот факт, что расстояния всегда положительны, поэтому, если расстояние х длиннее, чем общее расстояние четвертой ближайшей точки, вычислять (a.y-b.y) *(a.y-b.y) + (a.z - b.z) * (a.z - b.z)
.
не нужно. Если вы выбираете подход, начинающийся только сх-значения, я бы также предложил изменить структуры данных.Вместо структуры для каждой точки используйте четыре массива: int *x, *y, *z, *indexes;
Это сделает код более удобным для кеша. (И да, между указателями и массивами есть различия, но здесь это было не так важно)
Приведенные выше методы довольно просты.Если вы хотите продвинуться дальше, вы можете использовать эту идею.
- Разделите пространство на сетку 3D-блоков.
- Вычислите, какие точки принадлежат к данному блоку, и сохранитеинформация.
Посмотрите на это изображение:
Например, если у вас есть точка в D4, и выЕсли вы хотите найти ближайших четырех соседей, и вы найдете соседа в D4, то вы знаете , что за пределами квадрата C3: E5 не может быть более близкого соседа.Точно так же точка в D4, у которой есть сосед в D3, не может иметь более близкого соседа за пределами области B3: F6.
Но первое, что нужно при оптимизации, это ВСЕГДА определить узкое место.Вы уверены, что это проблема?Вы говорите, что читаете данные из файла, и чтение одной строки из файла ДОЛЖНО быть медленнее, чем вычисление расстояния.