В хеш-таблице в качестве Value использую Datatable-ИндексСтроки, но проблема в том, что при удалении и добавлении строк в Datatable происходит переиндексация, при этом rowID присутствующих в Datatable строк не меняется.

Вопрос: Как получить доступ к rowID или может быть есть другое решение по взаимодействию Datatable & Hashtable ?

Требования к быстродействию Datatable предельно высоки, поэтому PrimaryKey и FindRows не применимы.

Здравствуйте gwi52, Вы писали :
> В хеш-таблице в качестве Value использую Datatable-ИндексСтроки, но

1. А Key???

> проблема в том, что при удалении и добавлении строк в Datatable

2. Что значит удаление???

> происходит переиндексация, при этом rowID присутствующих в Datatable
> строк не меняется.

3. Что такое "происходит переиндексация", чего переиндексация и что за
зверь такой rowID???

> Вопрос: Как получить доступ к rowID или может быть есть другое решение
> по взаимодействию Datatable & Hashtable ?
>
> Требования к быстродействию Datatable предельно высоки, поэтому
> PrimaryKey и FindRows не применимы.

4. С чего Вы сделали вывод что поиск по PK будет медленнее чем поиск
hashtable???

5. Код можно???

Здравствуйте, Ромашка, Вы писали:

Р>4. С чего Вы сделали вывод что поиск по PK будет медленнее чем поиск
Р>hashtable???
Будет-будет. Не в сто раз, конечно, но будет. В датасетах по определению присутствует оверхед как по памяти, так и по времени работы в силу их универсальности. Так что если автору топика нужна максимальная производительность доступа к данным (в чем не мешает убедиться при помощи профайлера), то датасеты не будут особенно хорошим решением.

P.S. Что там за RowId имелся в виду, я тоже не понял

Спасибо ребята за участие в моей беде.

Простой тест производительности дает такие результаты:
поиск строки на компе IV 2.4 Ггц в 100-строковой таблице со строкой из 8-ми полей
при помощи PrimaryKey происходит за 13-15 мкс, примерно также осуществляется выборка строки с использованием индексирующих массивов с сортировкой, что достаточно громоздко, а вот выборка строки из той же таблицы по индексу происходит за 0.5 мкс — почувствуйте разницу.

Поэтому я и решил использовать хеш-таблицу, в которой Key — это строковая конкатенация значений в ключевых колонках, а вот с Value-то и проблема. Если я пытаюсь записывать сюда индекс строки, то все работает до первого удаления какой-либо строки, после чего система сама меняет индексы строк, т.е. если до этого искомая строка находилась в 56 позиции, то после удаления, например, 41 строки искомая строка перемещается в 55 позицию, а в хеш-таблице-то я уже записал 56.
Тем не менее, при отладке я вижу у каждой строки свойство rowID, которое для каждой строки при всех манипуляциях со всеми остальными строками не меняется. Т.е. это идентификатор строки, который привязан именно к этой строке. Но, блин, не знаю как подлезть к этому идентификатору rowID.

Здравствуйте Mab, Вы писали :
> Р>4. С чего Вы сделали вывод что поиск по PK будет медленнее чем поиск
> Р>hashtable???
> Будет-будет. Не в сто раз, конечно, но будет. В датасетах по определению
> присутствует оверхед как по памяти, так и по времени работы в силу их
> универсальности. Так что если автору топика нужна максимальная
> производительность доступа к данным (в чем не мешает убедиться при
> помощи профайлера), то датасеты не будут особенно хорошим решением.

Боюсь, что оверхедом заниается, как раз, автор.
Поиск по индексу (а в индексе, скорее всего, тот же hashtable или
b-tree) строки в datatable врядли в худшую сторону отличается от поиска
строки в такой-же hashtable + вытягивание мее из datatable. Короче, что
в лоб, что по лбу.

Здравствуйте gwi52, Вы писали :
> Простой тест производительности дает такие результаты:
> поиск строки на компе IV 2.4 Ггц в 100-строковой таблице со строкой из
> 8-ми полей
> при помощи PrimaryKey происходит за 13-15 мкс, примерно также
> осуществляется выборка строки с использованием индексирующих массивов с
> сортировкой, что достаточно громоздко, а вот выборка строки из той же
> таблицы по индексу происходит за 0.5 мкс — почувствуйте разницу.

Код покажи.

> Поэтому я и решил использовать хеш-таблицу, в которой Key — это
> строковая конкатенация значений в ключевых колонках, а вот с Value-то и
> проблема. Если я пытаюсь записывать сюда индекс строки, то все работает
> до первого удаления какой-либо строки, после чего система сама меняет
> индексы строк, т.е. если до этого искомая строка находилась в 56
> позиции, то после удаления, например, 41 строки искомая строка
> перемещается в 55 позицию, а в хеш-таблице-то я уже записал 56.

Код покажи. Никуда строки не перемещаются.

Здравствуйте, Ромашка, Вы писали:

Р>Поиск по индексу (а в индексе, скорее всего, тот же hashtable или
Р>b-tree)
Ни то, ни другое. Там красно-черное дерево.

Дело не в асимптотике, в обоих случаях она весьма хорошая. Дело в константе, которая там скрыта. Код поиска в Hashtable я могу окинуть одним взглядом. Код поиска по primarykey я начал было смотреть рефлектором, так пришлось залезать очень глубоко во внутренности ADO.NET (DataRowCollection.Find -> DataTable.FindByPrimaryKey -> DataTable.FindRow -> Index.FindRecords -> Index.FindNodeByKey -> RBTree -> ...). И на каждом шаге что-то авжное делается, причем зачастую полиморфно. Конверты, касты, проверки на порядок сортировки итп. Отсюда и торможение.

Автор утверждает, что различие по скорости в 20 раз. Априори не вижу в этом ничего удивительного.

Все это относится конкретно к поиску. Вытягивание данных, конечно, никаким hashtable-ом не ускоришь.

Щас, маленько подождите, приготовлю оба кода — с ДатаТабле и с тестером

Здравствуйте Mab, Вы писали :
> Автор утверждает, что различие по скорости в 20 раз. Априори не вижу в
> этом ничего удивительного.

Ну, у автора 8 столбцов в PK и неизвестно (пока) что в коде. Кто ж тут
телепатом работает??? Набросал шустрик по одному столбцу (int). На
миллионе записей результаты вполне так себе сравнимые (15:32 при
последовательных значениях и 78:46 на случайных).

Сори, Слегка прип*зднился.
Вот текст. Громозковато, но зато все.
Буду благодарен за советы.


using System;
using System.Collections;
using System.ComponentModel;
using System.Windows.Forms;
using System.Data;

public class Table : DataTable
{
public DataColumn A, B, P, Q, R, S, T, U; public DataColumn [] Keys=new DataColumn[2];
public Table Create ( out DataView Dv )
{
A=new DataColumn(); A.DataType=System.Type.GetType("System.Int32"); A.ColumnName="A"; this.Columns.Add (A); // 0
B=new DataColumn(); B.DataType=System.Type.GetType("System.String"); B.ColumnName="B"; this.Columns.Add (B); // 1
P=new DataColumn(); P.DataType=System.Type.GetType("System.Double"); P.ColumnName="P"; this.Columns.Add (P); // 2
Q=new DataColumn(); Q.DataType=System.Type.GetType("System.Int32"); Q.ColumnName="Q"; this.Columns.Add (Q); // 3
R=new DataColumn(); R.DataType=System.Type.GetType("System.TimeSpan");R.ColumnName="R"; this.Columns.Add (R); // 4
S=new DataColumn(); S.DataType=System.Type.GetType("System.Double"); S.ColumnName="S"; this.Columns.Add (S); // 5
T=new DataColumn(); T.DataType=System.Type.GetType("System.Double"); T.ColumnName="T"; this.Columns.Add (T); // 6
U=new DataColumn(); U.DataType=System.Type.GetType("Sytem.String"); U.ColumnName="U"; this.Columns.Add (U); // 7
Keys[0]=A; Keys[1]=B; PrimaryKey=Keys;
Dv=DefaultView; AcceptChanges (); return this;
} }
#endregion
public class Form1 : Form
{ public Form1() { InitializeComponent(); }
#region Controls
private System.Windows.Forms.Button btStart;
private System.Windows.Forms.TextBox tbExampleNum;
private System.Windows.Forms.TextBox tbExeTime;
private System.Windows.Forms.TextBox tbN;
private System.Windows.Forms.ToolTip toolTip1;
private System.Windows.Forms.Label lbMkc;
#endregion
#region WindowsFormDesign
private System.ComponentModel.IContainer components;
protected override void Dispose( bool disposing ){if( disposing){if (components!= null){components.Dispose();}}}base.Dispose(disposing);}
/// <summary>
/// Required method for Designer support — do not modify
/// the contents of this method with the code editor.
/// </summary>
private void InitializeComponent()
{
this.components = new System.ComponentModel.Container();
this.toolTip1 = new System.Windows.Forms.ToolTip(this.components);
this.tbExeTime = new System.Windows.Forms.TextBox();
this.tbN = new System.Windows.Forms.TextBox();
this.tbExampleNum = new System.Windows.Forms.TextBox();
this.btStart = new System.Windows.Forms.Button();
this.lbMkc = new System.Windows.Forms.Label();
this.SuspendLayout();
//
// tbExeTime
//
this.tbExeTime.Location = new System.Drawing.Point(136, 16);
this.tbExeTime.Name = "tbExeTime";
this.tbExeTime.Size = new System.Drawing.Size(88, 20);
this.tbExeTime.TabIndex = 3;
this.tbExeTime.Text = "";
this.toolTip1.SetToolTip(this.tbExeTime, "Время единичного исполнения ");
//
// tbN
//
this.tbN.Location = new System.Drawing.Point(48, 16);
this.tbN.Name = "tbN";
this.tbN.Size = new System.Drawing.Size(88, 20);
this.tbN.TabIndex = 4;
this.tbN.Text = "10000000";
this.toolTip1.SetToolTip(this.tbN, "Количество циклов накопления");
//
// tbExampleNum
//
this.tbExampleNum.Location = new System.Drawing.Point(8, 16);
this.tbExampleNum.Name = "tbExampleNum";
this.tbExampleNum.Size = new System.Drawing.Size(40, 20);
this.tbExampleNum.TabIndex = 6;
this.tbExampleNum.Text = "900";
this.toolTip1.SetToolTip(this.tbExampleNum, "Номер образца");
//
// btStart
//
this.btStart.Location = new System.Drawing.Point(256, 16);
this.btStart.Name = "btStart";
this.btStart.Size = new System.Drawing.Size(56, 23);
this.btStart.TabIndex = 2;
this.btStart.Text = "Пуск";
this.btStart.Click += new System.EventHandler(this.btStart_Click);
//
// lbMkc
//
this.lbMkc.ImageAlign = System.Drawing.ContentAlignment.MiddleRight;
this.lbMkc.Location = new System.Drawing.Point(224, 24);
this.lbMkc.Name = "lbMkc";
this.lbMkc.Size = new System.Drawing.Size(24, 16);
this.lbMkc.TabIndex = 7;
this.lbMkc.Text = "мкс";
//
// Form1
//
this.AutoScaleBaseSize = new System.Drawing.Size(5, 13);
this.ClientSize = new System.Drawing.Size(320, 53);
this.Controls.Add(this.lbMkc);
this.Controls.Add(this.tbExampleNum);
this.Controls.Add(this.tbN);
this.Controls.Add(this.tbExeTime);
this.Controls.Add(this.btStart);
this.Name = "Form1";
this.Text = "Проба";
this.ResumeLayout(false);

}
#endregion
static void Main () { Application.Run(new Form1()); }
private void btStart_Click ( object sender, EventArgs e )
{ DateTime begTime, endTime; TimeSpan exeTime; ArrayList aL=new ArrayList(); DataRow r; int i; int N=Convert.ToInt32(tbN.Text);
Table dt=new Table(); DataView dv; dt.Create(out dv); Hashtable ht=new Hashtable(); double Tmks; // Время исполнения одного цикла (мксек)
for ( i=0; i<100; i++) // Подготовка таблиц
{ r=dv.Table.NewRow(); r[0]=i.ToString(); r[1]=i; r[2]=(double)i; r[3]=i; r[4]=new TimeSpan(10,10,10); r[5]=(double)i; r[6]=(double)i;
r[7]=i.ToString(); dv.Table.Rows.Add(r); ht.Add( r[0].ToString()+r[1].ToString(), i );
}
begTime=DateTime.Now; r=dv.Table.NewRow(); // мксек //
// object[] findVals=new object[2]; findVals[0]=99; findVals[1]="99";
// for ( i=0; i<N; i++ ) { r = dv.Table.Rows.Find (findVals); } // 5.0000 // Поиск по PrimaryKey
// for ( i=0; i<N; i++ ){ r=dt.Rows[99]; } // 0.0500 // Выборка по индексу
// for ( i=0; i<N; i++ ){ if (ht.ContainsKey("5050")) { r=dt.Rows[(int)ht["5050"]];}} // 0.5000 // Тоже выборка по индексу, но с использованием хеш-таблицы
// for ( i=0; i<N; i++ ){ if (ht.ContainsKey("5051")) { r=dt.Rows[(int)ht["5051"]];}} // 0.1500 // Тоже самое, но с использованием несуществующего Key, т.е.реального поиска в DataTable не происходит
endTime=DateTime.Now; exeTime=endTime-begTime; Tmks=1000*exeTime.TotalMilliseconds / N; Tmks=Math.Round(Tmks,6); tbExeTime.Text=Tmks.ToString();

dt.Rows.RemoveAt(5); // dt.AcceptChanges(); // Проблема: Индексы в хеш-таблице сохранились, а в ДатаТабле переиндексировались,
for ( i=0; i<N; i++ ){ if (ht.ContainsKey("55")) { r=dt.Rows[(int)ht["55"]];}} // но rowID сохранились прежними. !?! Как до них достучаться !?!
}
}

Здравствуйте gwi52, Вы писали :
> Сори, Слегка прип*зднился.
> Вот текст. Громозковато, но зато все.
> Буду благодарен за советы.

Совет первый -- используй теги [ c # ] [ / c # ] (пробелы убрать)
Совет второй -- прекращай сравнивать сферических коней в вакууме

int id;
        Random random = new Random(1);
        // Поиск по PrimaryKey
        //6,829688
        object[] findVals=new object[2]; ;
        for ( i=0; i<N; i++ )
        {
            id = random.Next(100);
            findVals[0]= id; findVals[1]=id.ToString();
            r = dt.Rows.Find (findVals);
        }
        // Тоже выборка по индексу, но с использованием хеш-таблицы
        //1,9875
        string search;
        for ( i=0; i<N; i++ )
        {
            id = random.Next(100);
            search = id.ToString() + id.ToString();
            if (ht.ContainsKey(search))
                r=dt.Rows[(int)ht[search]];
        }

Что, в принципе, весьма ожидаемо при 100 строках. Но не в 10 же раз???
Попробуй увеличить количество строк -- цифры начнут сходится.

> Проблема: Индексы в хеш-таблице сохранились, а в ДатаТабле переиндексировались,
> // но rowID сохранились прежними. !?! Как до них достучаться !?!

А нафига??? Не легче ли в hashtable сразу ложить DataRow (или объект,
который из нее получается)???

    r=dv.Table.NewRow();
    r[0]=i.ToString();
//........
    dv.Table.Rows.Add(r);
    ht.Add(r[0].ToString()+r[1].ToString(), r);

Здравствуйте, Ромашка!
Ромашке.

Круглые кони... Это прекрасно... С квадратными копытами, зеленые такие...
Однако вернемся к нашим верблюдам...
Я преобразовал твою идею и получил примерно тот же результат, что и был, но отличающийся от твоего, что легко объяснимо —
в бесконечном цикле необходимо накапливать время только тестируемой операции, все остальное нужно выносить за его пределы.
Мысль о подмене Datatable хеш-таблицей не приемлема, поскольку смысл хеширования в том и заключается, чтобы, имея исходную структуру и используя все ее свойства и методы, ускорить только лишь поиск в ней.
Мне не нужна таблица большего размера, мне нужно максимальное быстродействие, при возможности добавления, удаления и сортировки строк, что и позволяет делать Дататабле.
Так что проблема и вопросы остаются.
С уважением, gwi52.


private void btStart_Click(object sender,EventArgs e)
{DateTime begTime,endTime; TimeSpan exeTime; ArrayList aL=new ArrayList(); DataRow r; int i; int N=Convert.ToInt32(tbN.Text);
Table dt=new Table(); DataView dv; dt.Create(out dv); Hashtable ht=new Hashtable(); double Tmks; // Время исполнения одного цикла (мксек)
Random random=new Random(1); string search=null;
object[] findVals=new object[2];
for (i=0; i<100; i++)
{ r=dv.Table.NewRow(); r[0]=random.Next(100); r[1]=random.Next(100).ToString(); r[2]=(double)i; r[3]=i; r[4]=new TimeSpan(10,10,10); r[5]=(double)i; r[6]=(double)i; r[7]=i.ToString(); dv.Table.Rows.Add(r);
ht.Add(r[0].ToString()+r[1].ToString(), i);
if (i==78){ findVals[0]=(int)r[0]; findVals[1]=(string)r[1]; search=r[0].ToString()+(string)r[1]; }
}
begTime=DateTime.Now; r=dv.Table.NewRow(); // мксек //
// for ( i=0; i<N; i++ ){ r=dt.Rows.Find (findVals); } // 3.78125 // 6,829688 // Поиск по PrimaryKey
for ( i=0; i<N; i++ ){ if (ht.ContainsKey(search)) r=dt.Rows[(int)ht[search]];} // 0.41406 // 1,9875 // Тоже выборка по индексу, но с использованием хеш-таблицы
endTime=DateTime.Now; exeTime=endTime-begTime; Tmks=1000*exeTime.TotalMilliseconds / N; Tmks=Math.Round(Tmks,6); tbExeTime.Text=Tmks.ToString();
// dt.Rows.RemoveAt(5); // dt.AcceptChanges(); // Проблема: Индексы в хеш-таблице сохранились, а в ДатаТабле переиндексировались,
// if (ht.ContainsKey("55")) r=dt.Rows[(int)ht["55"]]; // но rowID сохранились прежними. !?! Как до них достучаться !?!
}

Здравствуйте gwi52, Вы писали :
> Мысль о подмене Datatable хеш-таблицей не приемлема, поскольку смысл
> хеширования в том и заключается, чтобы, имея исходную структуру и
> используя все ее свойства и методы, ускорить только лишь поиск в ней.

Я не предлагал использовать хештаблицу вместо дататабле. Я предложил
тебе в хештабле хранить не индекс строки, а ссылку на нее. Какие проблемы???

Здравствуйте, Ромашка, Вы писали:

Р>Здравствуйте gwi52, Вы писали :
>> Мысль о подмене Datatable хеш-таблицей не приемлема, поскольку смысл
>> хеширования в том и заключается, чтобы, имея исходную структуру и
>> используя все ее свойства и методы, ускорить только лишь поиск в ней.

Р>Я не предлагал использовать хештаблицу вместо дататабле. Я предложил
Р>тебе в хештабле хранить не индекс строки, а ссылку на нее. Какие проблемы???

Что значит "ссылка на строку"?
Это, в моем понимании, либо индекс строки в Дататабле, что уже рассматривалось, либо rowID, что мне и хотелась бы увидеть, но не могу, в чем и вопрос.
Может я чего не догоняю. Растолкуй, а лучше кинь код.

Здравствуйте gwi52, Вы писали :
> Может я чего не догоняю. Растолкуй, а лучше кинь код.

Я тебе весь код уже написал. Ссылка на объект DataRow у тебя все так же
будет в DataTable, просто такую же ссылку ты запихнешь в хештаблицу. Че
ты дергать будешь объект через DataTable[index], что через
Hashtable[key] монопенисуально -- обе ссылки будут указывать на одну
и ту же DataRow, которая спокойно будет валяться где-то в памяти
компутера по адресу ссылки. А более подробно по поводу типов читай
тут

Автор(ы): Андрей Мартынов
Дата: 08.04.2003
Начиная программировать в среде .Net, довольно часто сталкиваешься с трудностями, в основе которых лежит недостаточно чёткое понимание различий в свойствах ссылочных типов (reference based types) и типов-значений (value based types). Между тем, мотивация применять типы-значения велика, т.к. умелое применение типов-значений может существенно повысить эффективность программного кода. Однако необходимо постоянно помнить, что типы-значения имеют ряд особенностей, которые необходимо учитывать как при разработке (определении) этих типов, так и при их использовании. Эти особенности value-типов и их отличия от ссылочных типов рассмотрены ниже.

Здравствуйте, Ромашка, Вы писали:

Р>Я тебе весь код уже написал. Ссылка на объект DataRow у тебя все так же
Р>будет в DataTable, просто такую же ссылку ты запихнешь в хештаблицу. Че
Р>ты дергать будешь объект через DataTable[index], что через
Р>Hashtable[key] монопенисуально -- обе ссылки будут указывать на одну
Р>и ту же DataRow, которая спокойно будет валяться где-то в памяти
Р>компутера по адресу ссылки. А более подробно по поводу типов читай
Р>тут

Автор(ы): Андрей Мартынов
Дата: 08.04.2003
Начиная программировать в среде .Net, довольно часто сталкиваешься с трудностями, в основе которых лежит недостаточно чёткое понимание различий в свойствах ссылочных типов (reference based types) и типов-значений (value based types). Между тем, мотивация применять типы-значения велика, т.к. умелое применение типов-значений может существенно повысить эффективность программного кода. Однако необходимо постоянно помнить, что типы-значения имеют ряд особенностей, которые необходимо учитывать как при разработке (определении) этих типов, так и при их использовании. Эти особенности value-типов и их отличия от ссылочных типов рассмотрены ниже.

"монопенисуально" — вопрос конечно интересный ..., полиписуально — это групповуха, не иначе

Идею понял, но реализация не получается
При формировании ht
ht.Add(r[0].ToString()+r[1].ToString(), r);
записываются строки, а не ссылки
а вот как записывать туда ссылки не понятно.

Здравствуйте, Ромашка, Вы писали:

Р>Здравствуйте gwi52, Вы писали :
>> Может я чего не догоняю. Растолкуй, а лучше кинь код.

Р>Я тебе весь код уже написал. Ссылка на объект DataRow у тебя все так же
Р>будет в DataTable, просто такую же ссылку ты запихнешь в хештаблицу. Че
Р>ты дергать будешь объект через DataTable[index], что через
Р>Hashtable[key] монопенисуально -- обе ссылки будут указывать на одну
Р>и ту же DataRow, которая спокойно будет валяться где-то в памяти
Р>компутера по адресу ссылки. А более подробно по поводу типов читай
Р>тут

Автор(ы): Андрей Мартынов
Дата: 08.04.2003
Начиная программировать в среде .Net, довольно часто сталкиваешься с трудностями, в основе которых лежит недостаточно чёткое понимание различий в свойствах ссылочных типов (reference based types) и типов-значений (value based types). Между тем, мотивация применять типы-значения велика, т.к. умелое применение типов-значений может существенно повысить эффективность программного кода. Однако необходимо постоянно помнить, что типы-значения имеют ряд особенностей, которые необходимо учитывать как при разработке (определении) этих типов, так и при их использовании. Эти особенности value-типов и их отличия от ссылочных типов рассмотрены ниже.

Во всяком случае при выборке ругается нехорошими словами

r=dt.Rows[(int)ht[search]];

Здравствуйте gwi52, Вы писали :

    r = ht[search];

Здравствуйте gwi52, Вы писали :
> записываются строки, а не ссылки
> а вот как записывать туда ссылки не понятно.

Вот Фома неверующий...

Попробуй поменять какую-нибудь строку в DataTable и прочитать ее из
хештаблицы. Уверяю тебя -- это одна и та же DataRow.

Здравствуйте, Ромашка, Вы писали:

Р>Здравствуйте gwi52, Вы писали :
Р>

Р>    r = ht[search];
Р>

Блин, теперь понял. И время охренительное 0.811 мкс
Сенкью, сенкью, вери мач...