summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorjan.reininghaus <jan.reininghaus@8e3bb3c2-eed4-f18f-5264-0b6c94e6926d>2014-04-07 11:43:05 +0000
committerjan.reininghaus <jan.reininghaus@8e3bb3c2-eed4-f18f-5264-0b6c94e6926d>2014-04-07 11:43:05 +0000
commitbe12dd40cf8ee3fa7502f9db63c5ee064cbebf5b (patch)
tree81cd1465b8ecd5541e429e911fb02e7f797afb35
parent288c53602f408674247525f2c40dfbb70f703b28 (diff)
updated README
git-svn-id: https://phat.googlecode.com/svn/trunk@155 8e3bb3c2-eed4-f18f-5264-0b6c94e6926d
-rw-r--r--README1
1 files changed, 1 insertions, 0 deletions
diff --git a/README b/README
index 76616a2..5c19577 100644
--- a/README
+++ b/README
@@ -39,6 +39,7 @@ algorithm. We provide the following choices of representation classes:
* {{{vector_set}}}: Each column is a {{{std::set}}} of integers, with the same meaning as above. The matrix is stored as a {{{std::vector}}} of such columns.
* {{{vector_list}}}: Each column is a sorted {{{std::list}}} of integers, with the same meaning as above. The matrix is stored as a {{{std::vector}}} of such columns.
* {{{sparse_pivot_column}}}: The matrix is stored as in the vector_vector representation. However, when a column is manipulated, it is first converted into a {{{std::set}}}, using an extra data field called the "pivot column". When another column is manipulated later, the pivot column is converted back to the {{{std::vector}}} representation. This can lead to significant speed improvements when many columns are added to a given pivot column consecutively. In a multicore setup, there is one pivot column per thread.
+ * {{{heap_pivot_column}}}: The same idea as in the sparse version. Instead of a {{{std::set}}}, the pivot column is represented by a {{{std::priority_queue}}}.
* {{{full_pivot_column}}}: The same idea as in the sparse version. However, instead of a {{{std::set}}}, the pivot column is expanded into a bit vector of size n (the dimension of the matrix). To avoid costly initializations, the class remembers which entries have been manipulated for a pivot column and updates only those entries when another column becomes the pivot.
* {{{bit_tree_pivot_column}}} (default representation): Similar to the {{{full_pivot_column}}} but the implementation is more efficient. Internally it is a bit-set with fast iteration over nonzero elements, and fast access to the maximal element.