Что лучший способ состоит в том, чтобы создать разреженный массив в C++?
В Java все переменные, которые вы объявляете, на самом деле являются «ссылками» на объекты (или примитивы), а не самими объектами.
При попытке выполнить один метод объекта , ссылка просит живой объект выполнить этот метод. Но если ссылка ссылается на NULL (ничего, нуль, void, nada), то нет способа, которым метод будет выполнен. Тогда runtime сообщит вам об этом, выбросив исключение NullPointerException.
Ваша ссылка «указывает» на нуль, таким образом, «Null -> Pointer».
Объект живет в памяти виртуальной машины пространство и единственный способ доступа к нему - использовать ссылки this. Возьмем этот пример:
public class Some {
private int id;
public int getId(){
return this.id;
}
public setId( int newId ) {
this.id = newId;
}
}
И в другом месте вашего кода:
Some reference = new Some(); // Point to a new object of type Some()
Some otherReference = null; // Initiallly this points to NULL
reference.setId( 1 ); // Execute setId method, now private var id is 1
System.out.println( reference.getId() ); // Prints 1 to the console
otherReference = reference // Now they both point to the only object.
reference = null; // "reference" now point to null.
// But "otherReference" still point to the "real" object so this print 1 too...
System.out.println( otherReference.getId() );
// Guess what will happen
System.out.println( reference.getId() ); // :S Throws NullPointerException because "reference" is pointing to NULL remember...
Это важно знать - когда больше нет ссылок на объект (в пример выше, когда reference и otherReference оба указывают на null), тогда объект «недоступен». Мы не можем работать с ним, поэтому этот объект готов к сбору мусора, и в какой-то момент VM освободит память, используемую этим объектом, и выделит другую.
7 ответов
Для C++ карта работает хорошо. Несколько миллионов объектов не будут проблемой. 10 миллионов объектов заняли приблизительно 4,4 секунды и приблизительно 57 meg на моем компьютере.
Мое тестовое приложение следующие:
#include <stdio.h>
#include <stdlib.h>
#include <map>
class triple {
public:
int x;
int y;
int z;
bool operator<(const triple &other) const {
if (x < other.x) return true;
if (other.x < x) return false;
if (y < other.y) return true;
if (other.y < y) return false;
return z < other.z;
}
};
int main(int, char**)
{
std::map<triple,int> data;
triple point;
int i;
for (i = 0; i < 10000000; ++i) {
point.x = rand();
point.y = rand();
point.z = rand();
//printf("%d %d %d %d\n", i, point.x, point.y, point.z);
data[point] = i;
}
return 0;
}
Теперь для динамичного выбора количества переменных самое легкое решение состоит в том, чтобы представить индекс как строка , и затем использовать строку в качестве ключа для карты. Например, объект, расположенный в [23] [55], может быть представлен через "23,55" строка. Мы можем также расширить это решение для более высоких размеров; такой что касается трех измерений произвольный индекс будет похож "34,45,56". Простая реализация этой техники следующие:
std::map data<string,int> data;
char ix[100];
sprintf(ix, "%d,%d", x, y); // 2 vars
data[ix] = i;
sprintf(ix, "%d,%d,%d", x, y, z); // 3 vars
data[ix] = i;
Как общие рекомендации, метод с помощью строк в качестве индексов на самом деле очень медленный. Намного более эффективное, но в других отношениях эквивалентное решение состояло бы в том, чтобы использовать векторы/массивы. Нет абсолютно никакой потребности записать индексы в строке.
typedef vector<size_t> index_t;
struct index_cmp_t : binary_function<index_t, index_t, bool> {
bool operator ()(index_t const& a, index_t const& b) const {
for (index_t::size_type i = 0; i < a.size(); ++i)
if (a[i] != b[i])
return a[i] < b[i];
return false;
}
};
map<index_t, int, index_cmp_t> data;
index_t i(dims);
i[0] = 1;
i[1] = 2;
// … etc.
data[i] = 42;
Однако использование map на практике часто не очень эффективно из-за реализации с точки зрения сбалансированного дерева двоичного поиска. Лучшая структура данных выполнения в этом случае была бы хэш-таблицей, в соответствии с std::unordered_map.
Повышение имеет шаблонную реализацию BLAS, названной uBLAS, который содержит разреженную матрицу.
http://www.boost.org/doc/libs/1_36_0/libs/numeric/ublas/doc/index.htm
Маленькая деталь в индексном сравнении. Необходимо сделать, лексикографическое выдерживает сравнение, иначе:
a= (1, 2, 1); b= (2, 1, 2);
(a<b) == (b<a) is true, but b!=a
Редактирование: Таким образом, сравнение должно, вероятно, быть:
return lhs.x<rhs.x
? true
: lhs.x==rhs.x
? lhs.y<rhs.y
? true
: lhs.y==rhs.y
? lhs.z<rhs.z
: false
: false
Хэш-таблицы имеют быструю вставку и ищут. Вы могли записать простую хеш-функцию, так как Вы знаете, что имели бы дело только с целочисленными парами как ключи.
Лучший способ реализовать разреженные матрицы состоит в том, чтобы быть не реализовать их - по крайней мере не самостоятельно. Я предложил бы BLAS (который я думаю, часть LAPACK), который может обработать действительно огромные матрицы.
Since only values with [a][b][c]...[w][x][y][z] are of consequence, we only store the indice themselves, not the value 1 which is just about everywhere - always the same + no way to hash it. Noting that the curse of dimensionality is present, suggest go with some established tool NIST or Boost, at least read the sources for that to circumvent needless blunder.
If the work needs to capture the temporal dependence distributions and parametric tendencies of unknown data sets, then a Map or B-Tree with uni-valued root is probably not practical. We can store only the indice themselves, hashed if ordering ( sensibility for presentation ) can subordinate to reduction of time domain at run-time, for all 1 values. Since non-zero values other than one are few, an obvious candidate for those is whatever data-structure you can find readily and understand. If the data set is truly vast-universe sized I suggest some sort of sliding window that manages file / disk / persistent-io yourself, moving portions of the data into scope as need be. ( writing code that you can understand ) If you are under commitment to provide actual solution to a working group, failure to do so leaves you at the mercy of consumer grade operating systems that have the sole goal of taking your lunch away from you.