Некоторые из приведенных ниже шагов могут быть оптимизированы в том смысле, что вы можете выполнять некоторые из них при создании набора данных.Тем не менее, я предполагаю, что вам только что дали ряд очков, и вы должны найти, в какие ячейки они вписываются.Если вы можете внедрить свой собственный код в шаг, который строит граф, вы могли бы делать то, что я написал ниже, вместе с построением графа, а не после факта.
Вы застряли с грубой силой вВ случае, если вам просто даны данные, вы никак не можете узнать иначе, поскольку вам нужно хотя бы раз посетить каждую точку, чтобы выяснить, в какой ячейке она находится. Поэтому мы застряли с O (n).Если у вас есть какие-то другие знания, которые вы могли бы использовать, то вы могли бы их использовать - но так как это не было упомянуто в ОП, я буду считать, что мы застряли с грубой силой.
Стратегия высокого уровнябудет выглядеть следующим образом:
// 1) Set rectangle bounds to have minX/Y at +inf, and maxX/Y to be -inf
// or initialize it with the first point
// 2) For each point:
// Set the set the min with min(point.x, bounds.min.x)
// Same for the max as well
// 3) Now you have your bounds, you divide it by how many cells fit onto each
// axis while taking into account that you might need to round up with division
// truncating the results, unless you cast to float and ceil()
int cols = ceil(float(bounds.max.x - bounds.min.x) / CELL_WIDTH);
int rows = ceil(float(bounds.max.y - bounds.min.y) / CELL_HEIGHT);
// 4) You have the # of cells for the width and height, so make a 2D array of
// some sort that is w * h cells (each cell contains 32-bit int at least) and
// initialize to zero if this is C or C++
// 5) Figure out the cell number by subtracting the bottom left corner of our
// bounds (which should be the min point on the x/y axis that we found from (1))
for (Point p in points):
int col = (p.x - minX) / cellWidth;
int row = (p.y - minY) / cellHeight;
data[row][col]++;
Оптимизация :
Есть несколько способов ускорить это с моей головы:
Если у вас есть степени двойки с шириной / высотой ячейки, вы можете сделать небольшое смещение.Если это кратно десяти, это может ускорить процесс, если вы не используете C или C ++ , но я не профилировал это, так что, возможно, горячая точка в Java и тому подобное сделает это для вас в любом случае(и понятия не имею о Python).Опять же, 1 миллион точек должен быть довольно быстрым.
В начале нам не нужно проходить весь диапазон, мы могли бы просто изменить размер нашей таблицы и добавить новые строки и столбцы.если мы найдем большее значение.Таким образом, мы сделали бы только одну итерацию по всем точкам вместо двух.
Если вас не волнует использование дополнительного места и ваши цифры только положительные, вы можете избежатьшаг вычитания "перевести на начало", просто предполагая, что все уже относительно происхождения и не вычитается вообще.Вы можете избежать этого, изменив шаг (1) кода так, чтобы min начинался с 0 вместо inf (или с первой точки, если вы выбрали это).Однако это может быть плохо, если ваши точки действительно далеко на оси, и вы в конечном итоге создаете тонну пустых слотов.Вы бы знали ваши данные и возможно ли это.
Возможно, есть еще несколько вещей, которые можно сделать, но это поможет вам на правильном пути к эффективности с ними,Вы сможете вернуться к тому, к какой ячейке это относится.
РЕДАКТИРОВАТЬ : Предполагается, что у вас не будет действительно небольшой ширины ячейки по сравнению с размером сетки (как, например, вашширина составляет 100 единиц, но ваш график может охватывать 2 миллиона единиц).Если это так, то вам нужно изучить, возможно, разреженные матрицы.