الفريق العربي للبرمجةأرشيف المنتديات · 2000 – 2023
نسخة أرشيفية للقراءة فقط — التسجيل والمشاركة مغلقان، والمحتوى محفوظ كما كان.

كيفية البحث في TreeView نريد تنافس في سرعة البحث

مغلق
بدأه Wael Dalloul في 31 أغسطس 2006 · 21 رد · 3,662 مشاهدة · في لغة Delphi
مشاركة: واتساب X فيسبوك تيليجرام
#1 صاحب الموضوع

السلام عليكم

لقد قمت منذ فترة بكتابة خوارزمية للبحث ضمن TreeView و لايجاد Node المطلوبة بسرعة معقولة نوعا ما

و لكن اريد ان اتشارك معكم في الافكار كي نصل باذن الله الى افضل طريقة لعمل ذلك

الفكرة هي: لديك treeview تحتوي على مجموعة من Nodes نريد ان نبحث عن Node ما في هذه ال Treeview عن طريق Text

في حال تم ايجاد Node ننهي الاجرائية(function) و نعيد هذه ال Node و في حال لم نجد ال Node نعيد القيمة nil

هذه مشاركة سابقة /index.ph...ost&p=66190

تحتوي على خوارزمية بسيطة للبحث

و موقع About يحتوي ايضا على خوارزمية شبيهة بالسابقة Get TreeView Node By Text

كل واحد يضع خوارزمية لذلك و في النهاية نرى من هي اسرع خوارزمية! :D

ملاحظة: نريد هذا في دلفي و ليس BCB حيث هناك شيئ اسمه map و ما ادراك ما ال map (h)

رب اجعلني مقيم الصلاة ومن ذريتي ربنا وتقبل دعاء.

لا تنسى: "العقل مثل العضلة كلما استخدمته أكثر كلما ازدادت قوته"

#2

للرفع ...

ذكرتني بعضوتي السابقة ...

ولو وافيت ربك دون ذنب *** وناقشك الحساب إذاً هلكتا

ولم يظلمك في عملٍ ولكن *** عسير أن تقوم بما حملتا

#3

فكرة جيدة اخ وائل

ساحاول المشاركة خلال هذا الاسبوع لو وجدت وقت

d4baa0.gif
#4

شكراً اخ waeldalol

وحقيقة موضوع رائع ،، ارجوا ان نجد الكثير من نوعه

(( اعنقد لو وضعتها على سلسة موضوعات واسميتها دعوة للتفكير )) :D

عموماً هذه محاولتي

var
i:integer;
begin
for i:=0 to TreeView1.Items.Count-1 do
if UpperCase(TreeView1.Items.Text)=UpperCase(edit1.Text) then begin
TreeView1.Items.Selected:=True;
TreeView1.SetFocus;
Exit;
end;
ShowMessage('Not Found');

تحياتي surini

myblog
#5

من الأحسن الأبتعاد عن استعمال .items

واستخدام طريقة اخرى ليكون البحث اسرع

d4baa0.gif
#6
surini كتب:
شكراً اخ waeldalol

وحقيقة موضوع رائع ،، ارجوا ان نجد الكثير من نوعه

(( اعنقد لو وضعتها على سلسة موضوعات واسميتها دعوة للتفكير )) :D

عموماً هذه محاولتي

var
i:integer;
begin
for i:=0 to TreeView1.Items.Count-1 do
if UpperCase(TreeView1.Items.Text)=UpperCase(edit1.Text) then begin
TreeView1.Items.Selected:=True;
TreeView1.SetFocus;
Exit;
end;
ShowMessage('Not Found');

تحياتي surini

هذه نفس الطرق السابقة في البحث و هي المرور على كل العقد و من ثم في حال التطابق يتم الخروج و هذه مكلفة كثيرا للوقت

حيث انت فقط قمت بتبديل حلقة while ب for و هذه الطريقة سرعتها نفس السابقة.

و لكن فكر بطريقة اخرى افضل و لا تيأس :)

اقتباس
من الأحسن الأبتعاد عن استعمال .items

واستخدام طريقة اخرى ليكون البحث اسرع

جميل جدا :D

مثل ماذا؟ ما هي البنية التي تقترحها حيث هناك في BCB شيئ اسمه ال map و هي سريعة جدا , و على ما اعتقد لا يوجد بنية مشابهة في دلفي

رب اجعلني مقيم الصلاة ومن ذريتي ربنا وتقبل دعاء.

لا تنسى: "العقل مثل العضلة كلما استخدمته أكثر كلما ازدادت قوته"

#7

قد تستطيع تسريع عملية البحث قليلا ولكنها ستبقى عملية بحث وبالتالي ستبقى مكلفة خاصة مع ازدياد عدد العقد.

أما للحصول على سرعة فورية «بشرط أنك أنت من يضيف العقد على الشجرة» فذلك ممكن باستخدام تقنية caching باستخدام بنية map أو ما يشابهها «فهي بالنهاية LinkedList وغير مقتصرة على لغة C»

لذلك إن كانت عملية caching مسموحة فأصبحنا نتكلم عن موضوع آخر غير البحث أليس كذلك؟

تم تعديل هذه المشاركة بواسطة fh_feras في 2 سبتمبر 2006 في 12:51

#8

اعتقد الامر لايخص الدلفي بكثر مايخص انواع الTrees الموجوده

على ماأظن بأن اسرع خوارزمية بحث هي تخزين المعلومات على شكل Binary Search

#9
fh_feras كتب:
قد تستطيع تسريع عملية البحث قليلا ولكنها ستبقى عملية بحث وبالتالي ستبقى مكلفة خاصة مع ازدياد عدد العقد.

أما للحصول على سرعة فورية «بشرط أنك أنت من يضيف العقد على الشجرة» فذلك ممكن باستخدام تقنية caching باستخدام بنية map أو ما يشابهها «فهي بالنهاية LinkedList وغير مقتصرة على لغة C»

لذلك إن كانت عملية caching مسموحة فأصبحنا نتكلم عن موضوع آخر غير البحث أليس كذلك؟

المشاركة هي المنافسة في تسريع البحث يعني في النهاية سوف نقوم بوضع عدد من العقد و نقوم بفحص الخوارزميات التي تم تقديمها

و ننتناقش في افضل خوارزمية حتى نصل الى افضل طريقة

بالنسبة لل map هل يمكنك الشرح اكثر عن بنيتها فما زلت لا اعرف الا القليل عنها. اما بالنسبة

اقتباس
بشرط أنك أنت من يضيف العقد على الشجرة
لماذا هذا الشرط الا نستطيع اخذ العقد من treeview و وضعهم في map

بالنسبة الى

اقتباس
لذلك إن كانت عملية caching مسموحة فأصبحنا نتكلم عن موضوع آخر غير البحث أليس كذلك؟

سيئة عمل caching هو انّ ذلك سوف يستهلك مقدار كبير من الذاكرة في حال وجود عقد كبيرة و لكن يبقى انه كيف سوف تقوم بربط البنية الجديدة التي سوف تقوم بعملها مع treeview؟!

اقتباس
اعتقد الامر لايخص الدلفي بكثر مايخص انواع الTrees الموجوده

على ماأظن بأن اسرع خوارزمية بحث هي تخزين المعلومات على شكل Binary Search

انا معك انّ الموضوع لا يخص دلفي و انما هي انواع ال trees الموجودة لنقل اننا سوف نستخدم treeview الموجودة مع دلفي و لن نستخدم مكون اخر :D

اين سوف يتم تخزين المعلومات على شكل binary search اي ما هي البنية و كيف سوف تقوم بربط هذه البنية مع ال treeview لكي تحصل على ال node التي نبحث عنها

رب اجعلني مقيم الصلاة ومن ذريتي ربنا وتقبل دعاء.

لا تنسى: "العقل مثل العضلة كلما استخدمته أكثر كلما ازدادت قوته"

#10
اقتباس
لماذا هذا الشرط الا نستطيع اخذ العقد من treeview و وضعهم في map

ألا تظن أن هذه العملية مكلفة أكثر من البحث بحد ذاته, فأنت تقرأ وتكتب كل عناصر الشجرة

لذلك الشرط من أجل أن تتم الكتابة بنفس الوقت الذي يتم فيه تعبئة الشجرة وليس عند البحث

اقتباس
سيئة عمل caching هو انّ ذلك سوف يستهلك مقدار كبير من الذاكرة في حال وجود عقد كبيرة

نعم العملية تستهلك الذاكرة, ولكن عناصر الشجرة موجودة في الذاكرة أساسا ببنية List ونريد أن نضعها ببنية أخرى أي سنضاعف حجم الذاكرة المحجوز

اقتباس
ولكن يبقى انه كيف سوف تقوم بربط البنية الجديدة التي سوف تقوم بعملها مع treeview؟!

بسيطة, الربط على عنوان العقدة وهو pointer أي باستخدام اسم العقدة نصل إلى عنوانها أي مؤشر للعقدة

اقتباس
بالنسبة لل map هل يمكنك الشرح اكثر عن بنيتها فما زلت لا اعرف الا القليل عنها

Map is a Sorted Associative Container that associates objects of type Key with objects of type Data.

Map is a Pair Associative Container, meaning that its value type is pair<const Key, Data>.

It is also a Unique Associative Container, meaning that no two elements have the same key.

سأحاول إضافة المزيد لاحقا

تم تعديل هذه المشاركة بواسطة fh_feras في 2 سبتمبر 2006 في 14:42

#11
اقتباس
ألا تظن أن هذه العملية مكلفة أكثر من البحث بحد ذاته, فأنت تقرأ وتكتب كل عناصر الشجرة

لذلك الشرط من أجل أن تتم الكتابة بنفس الوقت الذي يتم فيه تعبئة الشجرة وليس عند البحث

انا قصدت ممكن عمل ذلك مرة واحدة يعني مثلا عند اول عملية بحث مثلا :D

اقتباس
ولكن عناصر الشجرة موجودة في الذاكرة أساسا ببنية List ونريد أن نضعها ببنية أخرى أي سنضاعف حجم الذاكرة المحجوز

معك حق اصبح هناك نسختين من البيانات.

اولا دعونا قبل ان نفكر في بنية تخزين جديدة ان نذكر ما هي عيوب list الموجودة و لماذا هي بطيئة في عملية البحث.

رب اجعلني مقيم الصلاة ومن ذريتي ربنا وتقبل دعاء.

لا تنسى: "العقل مثل العضلة كلما استخدمته أكثر كلما ازدادت قوته"

#12

محاولة اخرى من خلال استخدام BinarySearch

function BinarySearch(TreeView:TTreeView;const Text:string):integer;
var
  First, last, center, cmp: Integer;
begin

  Result  := -1;

  if TreeView.Items.Count = 0 then Exit;

  First := 0;
  last  := TreeView.Items.Count - 1;
  repeat
	center := (First + last) div 2;
	cmp   := lstrcmp(PChar(UpperCase(Text)), PChar(UpperCase(TreeView.Items.Text)));
	if cmp = 0 then
	begin
	  Result  := center;
	  Break;
	end
	else if cmp > 0 then
	  First := center + 1
	else
	  last := center - 1;
  until last < First;
end;

تحياتي surini

myblog
#13

السلام عليكم ورحمة الله وبركاته

من النقاش أنتم لا تريدون استخدام item وهي الوسيلة الوحيدة للوصول إلى الخاصية text

كذلك لا تحبذون تخزين البيانات مرة أخرى في وسيط آخرى والبحث لا بد أن يكون في الذاكرة أصلاً

لدي فكرة وهي تخزين محتوياتها في TStringStream 

var strm : TStringStream;
begin
  Strm := TStringStream.Create('');
  TreeView1.SaveToStream(strm);
end;

وبهذا نستطيع البحث في نص بالذاكرة وهذا يجعله سريع

ولكن كيف أتعرف على مكان العقدة وأبيها في الدفق .

في تخزين محتويات TreeView في ملف نصي تكون العقد مرتبة هي وأبناءها كما نرتب الكود !!! (tab)

root
	Q
		1-q
		2-q
	E
		1-e
sub
	www

كيف نحدد مكان العقدة من البحث في ملف أو دفق بهذه الهيئة

تم تعديل هذه المشاركة بواسطة أبو محمد اللحياني في 4 سبتمبر 2006 في 14:08

ولو وافيت ربك دون ذنب *** وناقشك الحساب إذاً هلكتا

ولم يظلمك في عملٍ ولكن *** عسير أن تقوم بما حملتا

#14
اقتباس
محاولة اخرى من خلال استخدام BinarySearch

فكرة جيدة ولكن هذه الطريقة تعتمد على أن تكون الشجرة مفروزة على الأسماء, ولا تعمل في حال لم تكن مفروزة

#15
fh_feras كتب:
فكرة جيدة ولكن هذه الطريقة تعتمد على أن تكون الشجرة مفروزة على الأسماء, ولا تعمل في حال لم تكن مفروزة

بالفعل ، حيث ان الفكرة تعتمد على التحرك ضمن نطاق التقارب

لن يعمل الكود بالشكل الصحيح الا بعدما تكون Tree

SortType=stText

تحياتي surini

myblog
#16

up

رب اجعلني مقيم الصلاة ومن ذريتي ربنا وتقبل دعاء.

لا تنسى: "العقل مثل العضلة كلما استخدمته أكثر كلما ازدادت قوته"

#17

السلام عليكم ورحمة الله وبركاته :

آآآآآآآآآآآآآآآه يا وائل .. أظن أنك تبرمج شجرة حسابات , أليس كذلك ولا أنا غلطان ؟؟ ;)

فكرة جميلة أنا سأتابع الموضوع ولكن عن بعد لأنني أصبحت مفجولاً دوت نتياً

بالتوفيق :)

تم تعديل هذه المشاركة بواسطة imadouzoun في 30 أكتوبر 2006 في 04:54

دروس و كتب مفيدة----------------------كتيب الإجرائيات المخزنةتعرف على اللغة Transact SQL <<-->> كتيب عن تنصيب قواعد البيانات Sql Server باللغة العربية كتيب عن إنشاء قواعد البيانات في SQL Server باللغة العربية <<-->> درس مع الأمثلة عن المؤشرات و التعامل معها في الـ T-SQLالعبارات الشرطية و الحلقات في T-SQL <<-->> شرح لبعض الـ Extended Stored Procedure استخدام مكتبات الـ Dot Net الخاصة بك في الـ Sql Server 2005 <<-->> التعامل مع المصفوفات من خلال الـ T-SQLتعابير الجداول الشائعة في SQL Server 2005 <<-->>الاتصال بالأداة SQL Server Management Studioحلول سريعة و لمحات برمجية --------------------------------التصدير إلى إكسل : طريقة أولى : طريقة بسطر واحد من الكود <<-->> طريقة ثانية : طريقة تحتاج إنشاء إجرائية مخزنةً تجهيز بيانات جدول بالصيغة XML تمهيداً لحفظها كملف <<-->> تصدير البيانات إلى ملفات نصية برمجياً إغلاق جميع الإتصالات المفتوحة بقاعدة بيانات محددة .. تمهيداً لاسترجاعها أو حذفها <<-->> الاستعلام بناء على وقت مخزن بالصيغة العربية ضمن حقل نصي ..حذف السجلات المتكررة و إبقاء عدد محدد منها في جدول.. <<-->> أسرع طريقة لحذف سجلات جدول كيف احصل على اسم جهازي والباسوورد باستخدام T-SQL <<-->> حشر أنواع الصور المختلفة في حقل من نوع Image باستخدام إجرائية مخزنة .كيف تعرف أنواع الصور المخزنة في حقل من نوع Image .. <<-->> إجرائيات مخزنة ببارامترات ديناميكية مفيدة جداً للاستعلامات استخدام رقم الحقل بدلاً من الإسم في عبارات الإستعلام <<-->> من هو أضخم الجداول في قاعدة بياناتي ؟معرفة زمن تنفيذ الإجرائيات ( لتختار الطريقة الأسرع بين إجرائياتك المخزنة ) <<-->> التعامل مع الـ Rules برمجياً الحصول على آخر صف في الجدول <<-->> قراءة ملفات XML باستخدام T-SQL برمجياً (مثال مرفق)سحب بيانات ملف إكسل إلى الـ SQL Server <<-->> تشفير النسخة الاحتياطية بكلمة مرور <<-->> التخلص من البيانات المكررة <<-->> حل مشكلة التاريخ الهجريDifferential Backup بالتعريف---------- لا إله إلا الله .. محمد رسول الله

أخوكم في الله..  Imad Ozone

#18

مستحيل يا وائل لقد كنت أفكر في نبش هذا الموضوع ورفعه :D

سأضع محاولة بعد قليل, ترقبوا :D

#19

فيما يلي مثال يعتمد على فكرة تخزين Cache للعقد الموجودة في الشجرة أثناء إضافة هذه العقد

حيث إذا وضعنا عملية Cache عند الإضافة «والتعديل والحذف» يكون الوقت الصغير المستهلك في عملية Cache مهملا

علما أنه يمكن أن يتم بناء Cache عند أول عملية بحث ولكن عندها سيكون الوقت طويلا لأننا نعمل Cache لكل العقد والوقت الصغير المستهلك سوف يتجمع لكل العقد ليصبح وقتا كبيرا

البنية المستخدمة لعملية Cache هي StringList مفروزة حيث تحوي عناصرها نص العقدة ومؤشر على العقدة بحيث يكون نص العقدة هو المفتاح للوصول لمؤشر العقدة

ملاحظة: المثال يفترض عدم وجود عقدتين بنفس الاسم ولن يعمل إلا تحت هذه الفرضية

TreeTest.zip

تم تعديل هذه المشاركة بواسطة fh_feras في 31 أكتوبر 2006 في 23:03

#20
اقتباس
البنية المستخدمة لعملية Cache هي StringList مفروزة حيث تحوي عناصرها نص العقدة ومؤشر على العقدة بحيث يكون نص العقدة هو المفتاح للوصول لمؤشر العقدة

جميل جدا اخي fh_feras جربت المثال ,و وجدت انه مهما كان عدد العناصر في Tree فان الزمن اللازم للبحث هو صفر :D استغربت كثيرا من الامر

ثم رجعت الى الكود ووجدت انك وضعت التابع gettickcount قبل البحث, اي قبل تنفيذ عملية البحث لذلك يكون الزمن اللازم لذلك دائما هو صفر :lol:

بس ما تكون مقصودة :o لكي تظهر هي دائما صفر لكي تكون اسرع خوارزمية للبحث :P امزح

يبدو انّ عملية cache رهيبة جدا في عملية البحث, لاننا نستبدل Items ببنية اخرى تعطي امكانية اسرع في التحرك بين العقد من Items

سيئتها انها تأخذ مقدار اكبر من الذاكرة, و لكن حجم البيانات في الذاكرة ليس كبير فنحن لا نخزن سوى text لل item و بالتالي مهما بلغ عدد العقد من الكبر فذالك ليس مشكلة امام سرعة البحث التي نحصل عليها

نتائج البحث:

سرعة البحث باستخدام التقنية التقليدية اي(المرور على العقد من البداية و المقارنة) تكون اسرع عندما يكون موقع العقدة(item) التي نبحث عنها في البداية و كلما بعدت عن البداية يبطئ البحث و هكذا هذه تسمى بالبحث التسلسلي و هي لا تتطلب ان تكون قائمة العناصر مفروزة

سرعة البحث باستخدام تابع find لل stringlist وذلك بعد عمل cache تعتمد على البحث السريع

و هي نفس طريقة البحث المتبعة في مشاركة binary search للاخ surini حيث ايضا هو قام باستخدام البحث السريع

, وطبعا هي تتطلب ان تكون قائمة العناصر مفروزة

الفكرة التي في بالي و اريد ان اطبقها هي: القيام بعمل فهرسة مثل قواعد البيانات للنصوص و بالتالي يكون الوصول اليها اسرع من البحث السريع, حيث يتم استخدام trees للنصوص و بالتالي الوصول بشكل اسرع, لا احد يسرق الفكرة :D مع انها مشهورة :D

ما زال الباب مفتوحا لمن يريد ان يقدم طريقة بحث افضل, بالنهاية نريد ان يكون هناك مشاركات فيها تشغيل العقول و ازاحة الصدء :)

ملاحظة صغيرة: ان استخدام = للمقارنة بين الstrings هو ابطئ من استخدام التابع comparestr او التابع CompareString من API جرب ذلك و لكن ليس هناك فارق كبير في الوقت و لكنه اسرع

رب اجعلني مقيم الصلاة ومن ذريتي ربنا وتقبل دعاء.

لا تنسى: "العقل مثل العضلة كلما استخدمته أكثر كلما ازدادت قوته"

#21
اقتباس
رجعت الى الكود ووجدت انك وضعت التابع gettickcount قبل البحث
غريب لقد رجعت للكود الذي كتبته ووجدته صحيح وهذا هو جزء القياس
procedure TFormTreeTest.ButtonFindClick(Sender: TObject);
var
  i: Integer;
  t: Cardinal;
begin
  t:= GetTickCount;
  for i:= 0 to TreeViewTest.Items.Count - 1 do
	if TreeViewTest.Items.Item.Text = EditFind.Text then
	begin
	  t:= GetTickCount - t;
	  ShowMessage('Found in ' + IntToStr(t) + ' ms.');
	  if TreeViewTest.CanFocus then
		TreeViewTest.SetFocus;
	  TreeViewTest.Selected:= TreeViewTest.Items.Item;
	  Exit;
	end;
  t:= GetTickCount - t;
  ShowMessage('Not found in ' + IntToStr(t) + ' ms.');
end;

procedure TFormTreeTest.ButtonCacheFindClick(Sender: TObject);
var
  Index: Integer;
  t: Cardinal;
begin
  t:= GetTickCount;
  if TreeItemCache.Find(EditCacheFind.Text, Index) then
  begin
	t:= GetTickCount - t;
	ShowMessage('Found in ' + IntToStr(t) + ' ms.');
	if TreeViewTest.CanFocus then
	  TreeViewTest.SetFocus;
	TreeViewTest.Selected:= TreeItemCache.Objects[Index] as TTreeNode;
  end
  else
  begin
	t:= GetTickCount - t;
	ShowMessage('Not found in ' + IntToStr(t) + ' ms.');
  end;
end;

وكما تلاحظ فأنا أحسب الوقت بعد انتهاء البحث ثم أعرض رسالة ثم أقوم بتفعيل العقدة!

أنا اطلعت على النسخة التي لدي بصراحة ولا أتذكر إن كنت عدلت عليها بعد تحميلها :D فأرجو التوضيح

#22

كلامك صحيح, اختلط علي الامر لانني في الخوارزمية التي انشأتها للبحث, يكون الوقت بعد تحديد ال Item و ليس قبل تحديده, حيث اعتبرت ان عمل select لل item هو من ضمن الخوارزمية و لذلك التبس علي الامر.

انا اسف لم انتبه كثيرا الى ال :D code.

يعني الان ايجاد ال item يأخذ صفر على عدد كبير من ال items, بالفعل امر رهيب لم اكن اتخيل انّ الامر بهذه السرعة

سوف اقوم بتجريب الخوارزمية على Items تحوي نصوص كبيرة نوعا ما لارى إن كانت ستتغير هذه الصفر ام لا :D .

رب اجعلني مقيم الصلاة ومن ذريتي ربنا وتقبل دعاء.

لا تنسى: "العقل مثل العضلة كلما استخدمته أكثر كلما ازدادت قوته"

هذا الموضوع مغلق.

مواضيع مشابهة