如何排序 Eigen :: 有 标准 : pair <int, int > 并删除索引重复的 Matrix 。
原标题：How to sort the Eigen::Matrix that have std::pair<int, int> and delete the duplicates of indices
I need a way to sort and delete the duplicates of row and column indices of a sparse matrix. But at first I need to sort indices and later find a method to delete the duplicates.
Eigen::Matrix, Eigen::Dynamic, Eigen::Dynamic> unsorted_indices;
How can write a sort method for this? or method that I can achieve the both at once.
最佳回答
I can easily achieve this with std::set
> […] When unknows grow over a million then things are very costly
Matrix is the wrong data structure since you apparently make no use of it being two-dimensional. If std::set works for you, you can use a plain old std::vector
#include
std::vector> indices;
for(...)
indices.emplace_back(row_i, col_j);
std::sort(indices.begin(), indices.end());
indices.erase(std::unique(indices.begin(), indices.end()), indices.end());
indices.shrink_to_fit();
vector is more memory efficient than std::set. The erase(unique(…) stuff is known as the erase-remove idiom
Hash table
If the number of duplicates is large, removing them early with a set-like structure may be better. However, std::set has a relatively high memory overhead and costly O(log(n)) insertion cost. std::unordered_set is more efficient with O(1) and has slightly lower memory usage but it requires you to write your own hash function.
Unless you need to avoid external libraries, use a flat hash table. They have a much lower memory overhead. Boost comes with one that supports std::pair out-of-the-box:
#include
boost::unordered_flat_set> set;
for(...)
set.insert({row_i, col_j});
std::vector> indices(set.begin(), set.end());
std::sort(indices.begin(), indices.end());
Bitmap
As an alternative, you can use a simple bitmap. The memory consumption is then fixed to rows * cols / 8 byte as opposed to the at least 8 byte per entry in the hash table (not accounting for the hash table s overhead). So if your matrix is filled at least 1/64 (1.5%), the bitmap is more memory-efficient. Scanning it for set bits also automatically produces a sorted sequence, saving us this step.
#include
// C++20, using std::countr_zero
#include
// using std::uint32_t
std::size_t words = (rows * cols + 31) / 32;
std::vector bitmap(words);
for(...) {
std::size_t index = row_i * cols + col_j;
bitmap[index / 32] |= 1 << (index % 32);
}
std::vector> indices;
for(std::size_t i = 0; i < words; ++i) {
std::uint32_t word = bitmap[i];
while(word) {
std::uint32_t bit = std::countr_zero(word);
std::size_t index = i * 32 + bit;
int row_i = index / cols;
int col_j = index % cols;
indices.emplace_back(row_i, col_j);
word &= ~(1 << bit); // clear bit
}
}
问题回答
暂无回答
相关问题
How do I sort enum members alphabetically in Java?
I have an enum class like the following:
public enum Letter {
OMEGA_LETTER("Omega"),
GAMMA_LETTER("Gamma"),
BETA_LETTER("Beta"),
ALPHA_LETTER("Alpha"),
private final String ...
Grokking Timsort
There s a (relatively) new sort on the block called Timsort. It s been used as Python s list.sort, and is now going to be the new Array.sort in Java 7.
There s some documentation and a tiny Wikipedia ...
Sorting twodimensional Array in AS3
So, i have a two-dimensional Array of ID s and vote count - voteArray[i][0] = ID, voteArray[i][1] = vote count
I want the top 3 voted items to be displayed in different colors, so i have a 2nd Array -...
Linq operations against a List of Hashtables?
I m working with a set of legacy DAO code that returns an IList, where each Hashtable represents the row of a dynamically executed SQL query. For example, the List might contain the following records/...
C++ Array Sort Me
Stuck on an array sorter. Have to sort numbers from largest to smallest. I m trying two loops (one nested in the other). Here s the code:
int counter=0; // inner counter
int counter2=0; // outer ...
Can I Nest OrderBy in .NET?
This doesn t seem to work as I intend.
VB.NET:
Dim x = Model.Discussions.OrderByDescending(Function(d) d.Messages.OrderByDescending(Function(m) m.Sent).First.Sent)
For Each d As Discussion In x
....
sorting elements javascript
I m looking for a way to sort my elements, but it isn t as easy as it sounds. Please let me explain
My elements are grouped per 6 elements (thumbnails), each x represents a thumbnail However all ...
Objective-C, sorting an array based on a objects instance variable.
I m working on a game like Rodents Revenge, just to point out where I m coming from with this question. I m using the cocos2d game engine aswell...
I have a layer that contains about 168 blocks, ...
