أفضل طريقة لتخزين / الوصول إلى إخراج الرسم البياني

Question

ولدي حوالي 3500 مرافق السيطرة على الفيضانات التي أود أن يمثل كشبكة لتحديد مسارات التدفق (أساسا مخطط موجه). أنا حاليا باستخدام SQLSERVER وCTE لفحص متكرر كافة العقد ومكوناتها المنبع وهذا يعمل طويلة كما يفعل مسار المنبع ليس الكثير شوكة. ومع ذلك، بعض الاستفسارات تأخذ أضعافا مضاعفة أطول من غيرها حتى عندما لا تكون أبعد من ذلك بكثير بدنيا في الطريق (أي اثنين أو ثلاثة أجزاء "المصب") بسبب تعقيد المنبع المضافة؛ في بعض الحالات لقد ندعه يذهب أكثر من عشر دقائق قبل أن يقتل الاستعلام. أنا باستخدام جدول عمودين بسيط، عمود واحد يجري المرفق نفسه والآخر المرفق الذي هو المنبع من واحد المدرجة في العمود الأول.

وحاولت إضافة فهرس باستخدام منشأة الحالي للمساعدة في الأمور تسريع ولكن هذا لم يصنع فارقا. وكما للاتصالات ممكنة في الرسم البياني، فإن أي عقد يكون لديك عدة اتصالات المنبع ويمكن ان تكون مرتبطة إلى من عدة العقد "المصب".

ومن الممكن بالتأكيد أن هناك دورات في البيانات ولكن أنا لم ترد بعد على وسيلة جيدة للتحقق من ذلك (ما عدا عندما ذكرت الاستعلام CTE كحد أقصى عدد عودي ضرب، وتلك كانت سهلة لإصلاح)

وهكذا، سؤالي هو، أنا تخزين هذه المعلومات خاطئة؟ هل هناك طريقة أخرى أفضل من CTE للاستعلام عن نقاط المنبع؟

Answer 1

لا اعلم شيئا عن مرافق السيطرة على الفيضانات. ولكن أود أن أنتهز أول منشأة. واستخدام جدول مؤقت وحلقة في حين لتوليد المسار.

-- Pseudo Code
TempTable (LastNode, CurrentNode, N)


DECLARE @intN INT
SET @intN = 1

INSERT INTO TempTable(LastNode, CurrentNode, N)
  -- Insert first item in list with no up stream items...call this initial condition
  SELECT LastNode, CurrentNode, @intN
  FROM your table
  WHERE node has nothing upstream

WHILE @intN <= 3500
BEGIN
     SEt @intN = @intN + 1
    INSERT INTO TempTable(LastNode, CurrentNode, N)
      SELECT LastNode, CurrentNode, @intN
      FROM your table
      WHERE LastNode IN (SELECT CurrentNode FROM TempTable WHERE N = @intN-1)

IF @@ROWCOUNT = 0
     BREAK


END

إذا افترضنا أن كل نقطة عقدة لطفل واحد. ثم وهذا ينبغي أن لا تزيد عن 3500 التكرارات. إذا العقد متعددة لها نفس مزود المنبع بعد ذلك سوف يستغرق أقل. ولكن الأهم من ذلك، وهذا يتيح لك القيام بذلك ...

وSELECT LastNode، CurrentNode، N من TempTable ORDER BY N

والتي من شأنها أن تتيح لك معرفة ما إذا كان هناك أي حلقات أو أي قضايا أخرى مع موفر. بالمناسبة 3500 الصفوف ليست كثيرا حتى في أسوأ حالة كل مزود لافتا إلى مختلف مزود المنبع، وهذا لا ينبغي أن تأخذ هذا الوقت الطويل.

Answer 2

وأفضل وسيلة لتخزين الرسوم البيانية هي بالطبع لاستخدام الأصلي الرسم البياني ديسيبل: -)

ونلقي نظرة على neo4j . انها تنفذ في جاوة ولها بايثون وروبي الارتباطات كذلك.

وكتبت فوق صفحات الويكي اثنين مع أمثلة بسيطة من النماذج نطاق ممثلة الرسوم البيانية باستخدام neo4j: التجمع . تم العثور على مزيد من الأمثلة على معرض النمذجة نطاق الصفحة.

Answer 3

وتقليديا الرسوم البيانية إما يمثلها مصفوفة أو متجه. المصفوفة يأخذ مساحة أكبر، ولكن أسهل في عملية (3500x3500 الإدخالات في قضيتك)؛ متجه يأخذ مساحة أقل (3500 إدخالات، لكل واحد من قائمة الذين اتصالهم).

هل هذا مساعدتك؟

Answer 4

وأعتقد بنية البيانات الخاصة بك على ما يرام (ل SQL Server) ولكن CTE قد لا يكون الحل الأكثر فعالية لاستفساراتك. قد تحاول اتخاذ الإجراء المخزن الذي يخترق الرسم البياني باستخدام جدول مؤقت كما طابور بدلا من ذلك، وهذا ينبغي أن تكون أكثر كفاءة.

ويمكن أن تستخدم أيضا في جدول مؤقت للقضاء على دورات في الرسم البياني، على الرغم من أن لا يكون هناك أي

Answer 5

ونعم (ربما). مجموعة البيانات الخاص بك يبدو صغيرا نسبيا، هل يمكن تحميل الرسم البياني إلى الذاكرة كقائمة الجوار مصفوفة أو الجوار والاستعلام الرسم البياني مباشرة - على افتراض انك البرنامج.

وبقدر ما شكل على القرص، DOT هو محمول إلى حد ما / شعبية بين الآخرين. ويبدو أيضا شائعة جدا لتخزين قائمة الحواف في شكل ملف ثابت مثل:

vertex1 vertex2 {edge_label1}+

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

vertex1 vertex2
vertex2 vertex1

Answer 6

وتجربتي مع تخزين شيء من هذا القبيل وصفته أنت في قاعدة بيانات SQL Server:

وكنت تخزين المصفوفة بعد، نقول كم من الوقت يستغرق السفر من النقطة ألف إلى النقطة B. وقد فعلت تمثيل السذاجة وتخزينها مباشرة في جدول يسمى المسافات مع الأعمدة A، B، المسافة والوقت.

وهذا هو بطيء جدا على retreival بسيط. لقد وجدت أنه من الأفضل كثيرا لتخزين بلدي مصفوفة كاملة كنص. ثم إستعادة في الذاكرة قبل الحسابية، إنشاء struxture المصفوفة في الذاكرة والعمل معها هناك.

وأنا يمكن أن تقدم مع بعض الرموز، ولكن سيكون من C #.