Мне нужно поддерживать список подключенных клиентов, которые очень короткоживут и часто идут вверх и вниз. Из-за потенциального количества клиентов мне нужна коллекция, которая поддерживает быструю вставку/удаление. Предложения?
.net для быстрой вставки/удаления
Ответ 1
C5 Общая библиотека коллекции
Лучшие реализации, которые я нашел в С# и С++, - это для С#/CLI:
Он хорошо исследован, имеет расширяемые модульные тесты, и с февраля они также реализовали общие интерфейсы в .Net, что упрощает работу с коллекциями. Они были представлены на Channel9, и они провели обширное тестирование производительности в коллекциях.
Если вы используете структуры данных в любом случае, у этих исследователей есть red-black-tree в своей библиотеке, аналогично тому, что вы найдете, если вы запускаете отражатель Lütz и смотрите в System.Data внутренние структуры: p. Вставка-сложность: O (log (n)).
Коллекция С++ без блокировки
Затем, если вы можете разрешить некоторые комбинации С++, и вам абсолютно нужна скорость и вы хотите как можно меньше накладных расходов, бесплатные ADT от Дмитрия Вьюкова, вероятно, лучшее, что вы можете получить в этом мире, опережая конкурирующую библиотеку ADT от Intel.
Я прочитал некоторые из кода, и это действительно задатки того, кто хорошо разбирается в том, как эти вещи складываются. VС++ может использовать собственный С++-интерфейс без раздражающих границ. http://www.swig.org/ может в противном случае помочь вам обернуть интерфейсы С++ для потребления в .NET, или вы можете сделать это самостоятельно через P/Invoke.
Microsoft Take
Они написали учебники, SkipList в CodeProject, который очень хорошо полируется и реализует интерфейсы хорошо.) У них также есть несколько данных, структуры, связанные с .Net, а именно HashTable/Dictionary <, > и HashSet. Конечно, есть и тип ResizeArray/List, а также стек и очередь, но все они" линейны" при поиске.
Первичные инструменты Google
Если вы хотите ускорить время, необходимое для выделения памяти, вы можете использовать инструменты google. Они доступны в коде google и содержат очень интересную многопоточную malloc-реализацию (TCMalloc), которая показывает гораздо более последовательное время, чем обычный malloc делает. Вы можете использовать это вместе с незакрепленными структурами выше, чтобы действительно сходить с ума от производительности.
Улучшение времени ответа с помощью memoization
Вы также можете использовать memoization для функций для повышения производительности посредством кэширования, что-то интересное, если вы используете, например. F #. F # также позволяет взаимодействовать с С++, поэтому вы в порядке.
О (к)
Там также есть возможность сделать что-то самостоятельно, используя исследование, которое было сделано на bloom-filters, которые позволяют O (k) сложность поиска, где k - константа, зависящая от количества реализованных хэш-функций. Так было реализовано google BigTable. Этот фильтр предоставит вам элемент, если он в наборе или, возможно, с очень низкой вероятностью элемент, который не тот, который вы ищете (см. График в wikipedia - он приближается к P (wrong_key) → 0.01 как размер составляет около 10000 элементов, но вы можете обойти это, реализуя дополнительные хеш-функции/уменьшая набор.
Я не искал .Net реализаций этого, но поскольку расчеты хэширования независимы, вы можете использовать выполнение команды MS performance task задач, чтобы ускорить это.
"My" take - рандомизировать для достижения среднего значения O (log n)
Как бы то ни было, я просто занимался курсовой работой с использованием структур данных. В этом случае мы использовали С++, но очень легко перевести на С#. Мы построили три различные структуры данных; bloom-filter, skip-list и случайное двоичное дерево поиска.
См. код и анализ после последнего абзаца.
Аппаратные "коллекции"
Наконец, чтобы сделать мой ответ "полным", если вам действительно нужна скорость, вы можете использовать что-то вроде Таблицы маршрутизацииили Контент-адресная память. Это позволяет очень быстро O (1) в принципе получить "хэш-ориентированный" поиск ваших данных.
Случайный двоичный файл поиска/цветной фильтр С++ code
Мне бы очень понравилась обратная связь, если вы обнаружили ошибки в коде или просто указатели на то, как я могу сделать это лучше (или с лучшим использованием шаблонов). Обратите внимание, что фильтр цветения не похож на то, что он будет в реальной жизни; как правило, вам не нужно удалять из него, а затем гораздо гораздо эффективнее пространства, чем взломанный я, чтобы разрешить проверку на удаление.
DataStructure.h
#ifndef DATASTRUCTURE_H_
#define DATASTRUCTURE_H_
class DataStructure
{
public:
DataStructure() {countAdd=0; countDelete=0;countFind=0;}
virtual ~DataStructure() {}
void resetCountAdd() {countAdd=0;}
void resetCountFind() {countFind=0;}
void resetCountDelete() {countDelete=0;}
unsigned int getCountAdd(){return countAdd;}
unsigned int getCountDelete(){return countDelete;}
unsigned int getCountFind(){return countFind;}
protected:
unsigned int countAdd;
unsigned int countDelete;
unsigned int countFind;
};
#endif /*DATASTRUCTURE_H_*/
key.h
#ifndef KEY_H_
#define KEY_H_
#include <string>
using namespace std;
const int keyLength = 128;
class Key : public string
{
public:
Key():string(keyLength, ' ') {}
Key(const char in[]): string(in){}
Key(const string& in): string(in){}
bool operator<(const string& other);
bool operator>(const string& other);
bool operator==(const string& other);
virtual ~Key() {}
};
#endif /*KEY_H_*/
Key.cpp
#include "Key.h"
bool Key::operator<(const string& other)
{
return compare(other) < 0;
};
bool Key::operator>(const string& other)
{
return compare(other) > 0;
};
bool Key::operator==(const string& other)
{
return compare(other) == 0;
}
BloomFilter.h
#ifndef BLOOMFILTER_H_
#define BLOOMFILTER_H_
#include <iostream>
#include <assert.h>
#include <vector>
#include <math.h>
#include "Key.h"
#include "DataStructure.h"
#define LONG_BIT 32
#define bitmask(val) (unsigned long)(1 << (LONG_BIT - (val % LONG_BIT) - 1))
// TODO: Implement RW-locking on the reads/writes to the bitmap.
class BloomFilter : public DataStructure
{
public:
BloomFilter(){}
BloomFilter(unsigned long length){init(length);}
virtual ~BloomFilter(){}
void init(unsigned long length);
void dump();
void add(const Key& key);
void del(const Key& key);
/**
* Returns true if the key IS BELIEVED to exist, false if it absolutely doesn't.
*/
bool testExist(const Key& key, bool v = false);
private:
unsigned long hash1(const Key& key);
unsigned long hash2(const Key& key);
bool exist(const Key& key);
void getHashAndIndicies(unsigned long& h1, unsigned long& h2, int& i1, int& i2, const Key& key);
void getCountIndicies(const int i1, const unsigned long h1,
const int i2, const unsigned long h2, int& i1_c, int& i2_c);
vector<unsigned long> m_tickBook;
vector<unsigned int> m_useCounts;
unsigned long m_length; // number of bits in the bloom filter
unsigned long m_pockets; //the number of pockets
static const unsigned long m_pocketSize; //bits in each pocket
};
#endif /*BLOOMFILTER_H_*/
BloomFilter.cpp
#include "BloomFilter.h"
const unsigned long BloomFilter::m_pocketSize = LONG_BIT;
void BloomFilter::init(unsigned long length)
{
//m_length = length;
m_length = (unsigned long)((2.0*length)/log(2))+1;
m_pockets = (unsigned long)(ceil(double(m_length)/m_pocketSize));
m_tickBook.resize(m_pockets);
// my own (allocate nr bits possible to store in the other vector)
m_useCounts.resize(m_pockets * m_pocketSize);
unsigned long i; for(i=0; i< m_pockets; i++) m_tickBook[i] = 0;
for (i = 0; i < m_useCounts.size(); i++) m_useCounts[i] = 0; // my own
}
unsigned long BloomFilter::hash1(const Key& key)
{
unsigned long hash = 5381;
unsigned int i=0; for (i=0; i< key.length(); i++){
hash = ((hash << 5) + hash) + key.c_str()[i]; /* hash * 33 + c */
}
double d_hash = (double) hash;
d_hash *= (0.5*(sqrt(5)-1));
d_hash -= floor(d_hash);
d_hash *= (double)m_length;
return (unsigned long)floor(d_hash);
}
unsigned long BloomFilter::hash2(const Key& key)
{
unsigned long hash = 0;
unsigned int i=0; for (i=0; i< key.length(); i++){
hash = key.c_str()[i] + (hash << 6) + (hash << 16) - hash;
}
double d_hash = (double) hash;
d_hash *= (0.5*(sqrt(5)-1));
d_hash -= floor(d_hash);
d_hash *= (double)m_length;
return (unsigned long)floor(d_hash);
}
bool BloomFilter::testExist(const Key& key, bool v){
if(exist(key)) {
if(v) cout<<"Key "<< key<<" is in the set"<<endl;
return true;
}else {
if(v) cout<<"Key "<< key<<" is not in the set"<<endl;
return false;
}
}
void BloomFilter::dump()
{
cout<<m_pockets<<" Pockets: ";
// I changed u to %p because I wanted it printed in hex.
unsigned long i; for(i=0; i< m_pockets; i++) printf("%p ", (void*)m_tickBook[i]);
cout<<endl;
}
void BloomFilter::add(const Key& key)
{
unsigned long h1, h2;
int i1, i2;
int i1_c, i2_c;
// tested!
getHashAndIndicies(h1, h2, i1, i2, key);
getCountIndicies(i1, h1, i2, h2, i1_c, i2_c);
m_tickBook[i1] = m_tickBook[i1] | bitmask(h1);
m_tickBook[i2] = m_tickBook[i2] | bitmask(h2);
m_useCounts[i1_c] = m_useCounts[i1_c] + 1;
m_useCounts[i2_c] = m_useCounts[i2_c] + 1;
countAdd++;
}
void BloomFilter::del(const Key& key)
{
unsigned long h1, h2;
int i1, i2;
int i1_c, i2_c;
if (!exist(key)) throw "You can't delete keys which are not in the bloom filter!";
// First we need the indicies into m_tickBook and the
// hashes.
getHashAndIndicies(h1, h2, i1, i2, key);
// The index of the counter is the index into the bitvector
// times the number of bits per vector item plus the offset into
// that same vector item.
getCountIndicies(i1, h1, i2, h2, i1_c, i2_c);
// We need to update the value in the bitvector in order to
// delete the key.
m_useCounts[i1_c] = (m_useCounts[i1_c] == 1 ? 0 : m_useCounts[i1_c] - 1);
m_useCounts[i2_c] = (m_useCounts[i2_c] == 1 ? 0 : m_useCounts[i2_c] - 1);
// Now, if we depleted the count for a specific bit, then set it to
// zero, by anding the complete unsigned long with the notted bitmask
// of the hash value
if (m_useCounts[i1_c] == 0)
m_tickBook[i1] = m_tickBook[i1] & ~(bitmask(h1));
if (m_useCounts[i2_c] == 0)
m_tickBook[i2] = m_tickBook[i2] & ~(bitmask(h2));
countDelete++;
}
bool BloomFilter::exist(const Key& key)
{
unsigned long h1, h2;
int i1, i2;
countFind++;
getHashAndIndicies(h1, h2, i1, i2, key);
return ((m_tickBook[i1] & bitmask(h1)) > 0) &&
((m_tickBook[i2] & bitmask(h2)) > 0);
}
/*
* Gets the values of the indicies for two hashes and places them in
* the passed parameters. The index is into m_tickBook.
*/
void BloomFilter::getHashAndIndicies(unsigned long& h1, unsigned long& h2, int& i1,
int& i2, const Key& key)
{
h1 = hash1(key);
h2 = hash2(key);
i1 = (int) h1/m_pocketSize;
i2 = (int) h2/m_pocketSize;
}
/*
* Gets the values of the indicies into the count vector, which keeps
* track of how many times a specific bit-position has been used.
*/
void BloomFilter::getCountIndicies(const int i1, const unsigned long h1,
const int i2, const unsigned long h2, int& i1_c, int& i2_c)
{
i1_c = i1*m_pocketSize + h1%m_pocketSize;
i2_c = i2*m_pocketSize + h2%m_pocketSize;
}
** RBST.h **
#ifndef RBST_H_
#define RBST_H_
#include <iostream>
#include <assert.h>
#include <vector>
#include <math.h>
#include "Key.h"
#include "DataStructure.h"
#define BUG(str) printf("%s:%d FAILED SIZE INVARIANT: %s\n", __FILE__, __LINE__, str);
using namespace std;
class RBSTNode;
class RBSTNode: public Key
{
public:
RBSTNode(const Key& key):Key(key)
{
m_left =NULL;
m_right = NULL;
m_size = 1U; // the size of one node is 1.
}
virtual ~RBSTNode(){}
string setKey(const Key& key){return Key(key);}
RBSTNode* left(){return m_left; }
RBSTNode* right(){return m_right;}
RBSTNode* setLeft(RBSTNode* left) { m_left = left; return this; }
RBSTNode* setRight(RBSTNode* right) { m_right =right; return this; }
#ifdef DEBUG
ostream& print(ostream& out)
{
out << "Key(" << *this << ", m_size: " << m_size << ")";
return out;
}
#endif
unsigned int size() { return m_size; }
void setSize(unsigned int val)
{
#ifdef DEBUG
this->print(cout);
cout << "::setSize(" << val << ") called." << endl;
#endif
if (val == 0) throw "Cannot set the size below 1, then just delete this node.";
m_size = val;
}
void incSize() {
#ifdef DEBUG
this->print(cout);
cout << "::incSize() called" << endl;
#endif
m_size++;
}
void decrSize()
{
#ifdef DEBUG
this->print(cout);
cout << "::decrSize() called" << endl;
#endif
if (m_size == 1) throw "Cannot decrement size below 1, then just delete this node.";
m_size--;
}
#ifdef DEBUG
unsigned int size(RBSTNode* x);
#endif
private:
RBSTNode(){}
RBSTNode* m_left;
RBSTNode* m_right;
unsigned int m_size;
};
class RBST : public DataStructure
{
public:
RBST() {
m_size = 0;
m_head = NULL;
srand(time(0));
};
virtual ~RBST() {};
/**
* Tries to add key into the tree and will return
* true for a new item added
* false if the key already is in the tree.
*
* Will also have the side-effect of printing to the console if v=true.
*/
bool add(const Key& key, bool v=false);
/**
* Same semantics as other add function, but takes a string,
* but diff name, because that'll cause an ambiguity because of inheritance.
*/
bool addString(const string& key);
/**
* Deletes a key from the tree if that key is in the tree.
* Will return
* true for success and
* false for failure.
*
* Will also have the side-effect of printing to the console if v=true.
*/
bool del(const Key& key, bool v=false);
/**
* Tries to find the key in the tree and will return
* true if the key is in the tree and
* false if the key is not.
*
* Will also have the side-effect of printing to the console if v=true.
*/
bool find(const Key& key, bool v = false);
unsigned int count() { return m_size; }
#ifdef DEBUG
int dump(char sep = ' ');
int dump(RBSTNode* target, char sep);
unsigned int size(RBSTNode* x);
#endif
private:
RBSTNode* randomAdd(RBSTNode* target, const Key& key);
RBSTNode* addRoot(RBSTNode* target, const Key& key);
RBSTNode* rightRotate(RBSTNode* target);
RBSTNode* leftRotate(RBSTNode* target);
RBSTNode* del(RBSTNode* target, const Key& key);
RBSTNode* join(RBSTNode* left, RBSTNode* right);
RBSTNode* find(RBSTNode* target, const Key& key);
RBSTNode* m_head;
unsigned int m_size;
};
#endif /*RBST_H_*/
** RBST.cpp **
#include "RBST.h"
bool RBST::add(const Key& key, bool v){
unsigned int oldSize = m_size;
m_head = randomAdd(m_head, key);
if (m_size > oldSize){
if(v) cout<<"Node "<<key<< " is added into the tree."<<endl;
return true;
}else {
if(v) cout<<"Node "<<key<< " is already in the tree."<<endl;
return false;
}
if(v) cout<<endl;
};
bool RBST::addString(const string& key) {
return add(Key(key), false);
}
bool RBST::del(const Key& key, bool v){
unsigned oldSize= m_size;
m_head = del(m_head, key);
if (m_size < oldSize) {
if(v) cout<<"Node "<<key<< " is deleted from the tree."<<endl;
return true;
}
else {
if(v) cout<< "Node "<<key<< " is not in the tree."<<endl;
return false;
}
};
bool RBST::find(const Key& key, bool v){
RBSTNode* ret = find(m_head, key);
if (ret == NULL){
if(v) cout<< "Node "<<key<< " is not in the tree."<<endl;
return false;
}else {
if(v) cout<<"Node "<<key<< " is in the tree."<<endl;
return true;
}
};
#ifdef DEBUG
int RBST::dump(char sep){
int ret = dump(m_head, sep);
cout<<"SIZE: " <<ret<<endl;
return ret;
};
int RBST::dump(RBSTNode* target, char sep){
if (target == NULL) return 0;
int ret = dump(target->left(), sep);
cout<< *target<<sep;
ret ++;
ret += dump(target->right(), sep);
return ret;
};
#endif
/**
* Rotates the tree around target, so that target left
* is the new root of the tree/subtree and updates the subtree sizes.
*
*(target) b (l) a
* / \ right / \
* a ? ----> ? b
* / \ / \
* ? x x ?
*
*/
RBSTNode* RBST::rightRotate(RBSTNode* target) // private
{
if (target == NULL) throw "Invariant failure, target is null"; // Note: may be removed once tested.
if (target->left() == NULL) throw "You cannot rotate right around a target whose left node is NULL!";
#ifdef DEBUG
cout <<"Right-rotating b-node ";
target->print(cout);
cout << " for a-node ";
target->left()->print(cout);
cout << "." << endl;
#endif
RBSTNode* l = target->left();
int as0 = l->size();
// re-order the sizes
l->setSize( l->size() + (target->right() == NULL ? 0 : target->right()->size()) + 1); // a.size += b.right.size + 1; where b.right may be null.
target->setSize( target->size() -as0 + (l->right() == NULL ? 0 : l->right()->size()) ); // b.size += -a_0_size + x.size where x may be null.
// swap b left (for a)
target->setLeft(l->right());
// and a right (for b left)
l->setRight(target);
#ifdef DEBUG
cout << "A-node size: " << l->size() << ", b-node size: " << target->size() << "." << endl;
#endif
// return the new root, a.
return l;
};
/**
* Like rightRotate, but the other way. See docs for rightRotate(RBSTNode*)
*/
RBSTNode* RBST::leftRotate(RBSTNode* target)
{
if (target == NULL) throw "Invariant failure, target is null";
if (target->right() == NULL) throw "You cannot rotate left around a target whose right node is NULL!";
#ifdef DEBUG
cout <<"Left-rotating a-node ";
target->print(cout);
cout << " for b-node ";
target->right()->print(cout);
cout << "." << endl;
#endif
RBSTNode* r = target->right();
int bs0 = r->size();
// re-roder the sizes
r->setSize(r->size() + (target->left() == NULL ? 0 : target->left()->size()) + 1);
target->setSize(target->size() -bs0 + (r->left() == NULL ? 0 : r->left()->size()));
// swap a right (for b left)
target->setRight(r->left());
// swap b left (for a)
r->setLeft(target);
#ifdef DEBUG
cout << "Left-rotation done: a-node size: " << target->size() << ", b-node size: " << r->size() << "." << endl;
#endif
return r;
};
//
/**
* Adds a key to the tree and returns the new root of the tree.
* If the key already exists doesn't add anything.
* Increments m_size if the key didn't already exist and hence was added.
*
* This function is not called from public methods, it a helper function.
*/
RBSTNode* RBST::addRoot(RBSTNode* target, const Key& key)
{
countAdd++;
if (target == NULL) return new RBSTNode(key);
#ifdef DEBUG
cout << "addRoot(";
cout.flush();
target->print(cout) << "," << key << ") called." << endl;
#endif
if (*target < key)
{
target->setRight( addRoot(target->right(), key) );
target->incSize(); // Should I?
RBSTNode* res = leftRotate(target);
#ifdef DEBUG
if (target->size() != size(target))
BUG("in addRoot 1");
#endif
return res;
}
target->setLeft( addRoot(target->left(), key) );
target->incSize(); // Should I?
RBSTNode* res = rightRotate(target);
#ifdef DEBUG
if (target->size() != size(target))
BUG("in addRoot 2");
#endif
return res;
};
/**
* This function is called from the public add(key) function,
* and returns the new root node.
*/
RBSTNode* RBST::randomAdd(RBSTNode* target, const Key& key)
{
countAdd++;
if (target == NULL)
{
m_size++;
return new RBSTNode(key);
}
#ifdef DEBUG
cout << "randomAdd(";
target->print(cout) << ", \"" << key << "\") called." << endl;
#endif
int r = (rand() % target->size()) + 1;
// here is where we add the target as root!
if (r == 1)
{
m_size++; // TODO: Need to lock.
return addRoot(target, key);
}
#ifdef DEBUG
printf("randomAdd recursion part, ");
#endif
// otherwise, continue recursing!
if (*target <= key)
{
#ifdef DEBUG
printf("target <= key\n");
#endif
target->setRight( randomAdd(target->right(), key) );
target->incSize(); // TODO: Need to lock.
#ifdef DEBUG
if (target->right()->size() != size(target->right()))
BUG("in randomAdd 1");
#endif
}
else
{
#ifdef DEBUG
printf("target > key\n");
#endif
target->setLeft( randomAdd(target->left(), key) );
target->incSize(); // TODO: Need to lock.
#ifdef DEBUG
if (target->left()->size() != size(target->left()))
BUG("in randomAdd 2");
#endif
}
#ifdef DEBUG
printf("randomAdd return part\n");
#endif
m_size++; // TODO: Need to lock.
return target;
};
/////////////////////////////////////////////////////////////
///////////////////// DEL FUNCTIONS ////////////////////////
/////////////////////////////////////////////////////////////
/**
* Deletes a node with the passed key.
* Returns the root node.
* Decrements m_size if something was deleted.
*/
RBSTNode* RBST::del(RBSTNode* target, const Key& key)
{
countDelete++;
if (target == NULL) return NULL;
#ifdef DEBUG
cout << "del(";
target->print(cout) << ", \"" << key << "\") called." << endl;
#endif
RBSTNode* ret = NULL;
// found the node to delete
if (*target == key)
{
ret = join(target->left(), target->right());
m_size--;
delete target;
return ret; // return the newly built joined subtree!
}
// store a temporary size before recursive deletion.
unsigned int size = m_size;
if (*target < key) target->setRight( del(target->right(), key) );
else target->setLeft( del(target->left(), key) );
// if the previous recursion changed the size, we need to decrement the size of this target too.
if (m_size < size) target->decrSize();
#ifdef DEBUG
if (RBST::size(target) != target->size())
BUG("in del");
#endif
return target;
};
/**
* Joins the two subtrees represented by left and right
* by randomly choosing which to make the root, weighted on the
* size of the sub-tree.
*/
RBSTNode* RBST::join(RBSTNode* left, RBSTNode* right)
{
if (left == NULL) return right;
if (right == NULL) return left;
#ifdef DEBUG
cout << "join(";
left->print(cout);
cout << ",";
right->print(cout) << ") called." << endl;
#endif
// Find the chance that we use the left tree, based on its size over the total tree size.
// 3 s.d. randomness :-p e.g. 60.3% chance.
bool useLeft = ((rand()%1000) < (signed)((float)left->size()/(float)(left->size() + right->size()) * 1000.0));
RBSTNode* subtree = NULL;
if (useLeft)
{
subtree = join(left->right(), right);
left->setRight(subtree)
->setSize((left->left() == NULL ? 0 : left->left()->size())
+ subtree->size() + 1 );
#ifdef DEBUG
if (size(left) != left->size())
BUG("in join 1");
#endif
return left;
}
subtree = join(right->left(), left);
right->setLeft(subtree)
->setSize((right->right() == NULL ? 0 : right->right()->size())
+ subtree->size() + 1);
#ifdef DEBUG
if (size(right) != right->size())
BUG("in join 2");
#endif
return right;
};
/////////////////////////////////////////////////////////////
///////////////////// FIND FUNCTIONS ///////////////////////
/////////////////////////////////////////////////////////////
/**
* Tries to find the key in the tree starting
* search from target.
*
* Returns NULL if it was not found.
*/
RBSTNode* RBST::find(RBSTNode* target, const Key& key)
{
countFind++; // Could use private method only counting the first call.
if (target == NULL) return NULL; // not found.
if (*target == key) return target; // found (does string override ==?)
if (*target < key) return find(target->right(), key); // search for gt to the right.
return find(target->left(), key); // search for lt to the left.
};
#ifdef DEBUG
unsigned int RBST::size(RBSTNode* x)
{
if (x == NULL) return 0;
return 1 + size(x->left()) + size(x->right());
}
#endif
Я сохраню SkipList в другое время, так как уже можно найти хорошие реализации SkipList из ссылок, и моя версия не сильно отличается.
Графы, созданные из тестового файла, следующие:
График, показывающий время, необходимое для добавления новых элементов для BloomFilter, RBST и SkipList. graph http://haf.se/content/dl/addtimer.png
График, показывающий время, необходимое для поиска элементов для BloomFilter, RBST и SkipList graph http://haf.se/content/dl/findtimer.png
График, показывающий время, затраченное на удаление элементов для BloomFilter, RBST и SkipList graph http://haf.se/content/dl/deltimer.png
Итак, как вы можете видеть, случайное двоичное дерево поиска было намного лучше, чем SkipList. Фильтр цветения соответствует его O (k).
Ответ 2
Рассмотрим коллекции, основанные на хеше, для этого, например. HashSet, Dictionary, HashTable, которые обеспечивают постоянную производительность для добавления и удаления элементов.
Дополнительная информация из руководства разработчика .NET Framework:
Ответ 3
Ну, сколько вам нужно запросить? Связанный список имеет быструю вставку/удаление (в любой позиции), но не так быстро выполняет поиск (например) словаря/отсортированного списка. Альтернативно, прямой список с парой бит/значение в каждом - то есть "все еще имеет значение". Просто повторите использование логически пустых ячеек перед добавлением. Удалить просто очищает ячейку.
Для ссылочных типов здесь будет "null". Для значений-типов Nullable<T>.
Ответ 4
Вы можете использовать Hashtable или строго типизированный словарь <Client> . Класс клиента может переопределять GetHashCode для обеспечения более быстрого генерации хэш-кода, или если вы используете Hashtable, вы можете использовать IHashCodeProvider.
Ответ 5
Как вам нужно найти клиентов? Требуется ли кортеж/словарь? Вы, скорее всего, найдете что-то, что решает вашу проблему в библиотеке Jeffrey Richter Power Collections, которая имеет списки, деревья, большинство структур данных, которые вы может думать.
Ответ 6
Меня очень впечатлило интервью Channel9 с Питером Сестофтом:
channel9.msdn.com/shows/Going+Deep/Peter-Sestoft-C5-Generic-Collection-Library-for-C-and-CLI/
Он является профессором в Копенгагенском ИТ-университете, который помог создать коллекцию C6 Generic Collection:
Это может быть слишком много, или это может быть просто скорейшая коллекция, которую вы искали...
HTH,
-Mike