أكثر

شبكة جيران فعالة؟

شبكة جيران فعالة؟


أود تحديد جيران ترتيب Kth لحافة على شبكة ، وتحديداً جيران مجموعة كبيرة من الشوارع. على سبيل المثال ، لدي شارع أهتم بمشاهدته ، أطلق عليه اسم الشارع المحوري. لكل شارع محوري أريد أن أجد الشوارع التي تشترك في تقاطع ، هؤلاء هم الجيران من الدرجة الأولى. ثم بالنسبة لكل من تلك الشوارع التي تشترك في تقاطع مع الشارع المحوري ، أود أن أجد جيرانهم (سيكون هؤلاء هم الجيران من الدرجة الثانية) ، وهكذا ...

استغرق حساب الجيران من الدرجة الأولى باستخدام مكتبة المعالجة الجغرافية (arcpy) الخاصة بـ ArcGIS أكثر من 6 ساعات ، بينما يستغرق الجيران من الدرجة الثانية أكثر من 18 ساعة. لقد نشرت على هذا في منتديات ESRI هنا (يتضمن الرابط كود Arcpy الذي يعمل ولكنه بطيء للغاية). وغني عن القول أنني أريد إيجاد حل أكثر كفاءة. لقد قمت بإنشاء قاموس Python الذي تم ترميزه في كل شارع ويحتوي على الشوارع المتصلة كقيم. فمثلا:

st2neighs = {street1: [street2، street3، street5]، street2: [street1، street4]،…}.

الشارع 1 متصل بالشارع 2 ، 3 ، 5 ؛ الشارع 2 متصل بالشارع 1 و 4 ؛ إلخ ... يوجد حوالي 30000 شارع في منطقة الدراسة معظمها بها أقل من 7 شوارع متصلة. نسخة مخللة من البيانات المستخدمة في الكود أدناه موجودة هنا.

افترضت أن معرفة الجيران من الدرجة الأولى سيسمح لي بتتبع الجيران من الدرجة الأولى بكفاءة. لكن الكود التالي يقدم نتائج غير صحيحة:

## حدد جيران ترتيب K من مجموعة من الشوارع التي تم أخذ عينات منها. ## يحفظ بتنسيق القاموس بحيث يكون ## المفتاح هو الشارع الذي تم أخذ عينات منه والشوارع المجاورة هي القيم ################## ## مكتبات الاستيراد ##### ############# ################### seg_file = open ("seg2st.pkl"، "rb") st_file = open ("st2neighs.pkl"، "rb") seg2st = pickle.load (seg_file) st2neigh = pickle.load (st_file) ################## ## وظائف DEF ############## #### ## يأخذ في إملاء من المقاطع (مفتاح) وشوارعها (القيم). ## يُرجع العدد المطلوب من الشوارع التي تم أخذ عينات منها في كل مقطع ## يُرجع مقطعًا مرتبطًا بمفتاح إملاء يحتوي على عناصر tlids. def selectSample (seg2st ، nbirths): randSt = {} لـ segK في seg2st.iterkeys (): ranSamp = [int (random.choice (seg2st [segK])) لـ i في xrange (nbirths)] randSt [segK] = [ ] بالنسبة لـ aSamp في ranSamp: randSt [segK] .append (aSamp) إرجاع randSt ## يأخذ في قائمة بجميع الشوارع (المفاتيح) وجيرانها من الدرجة الأولى (القيم) ## يأخذ في قائمة الشوارع التي تم أخذ عينات منها ## يُرجع ديكت من جميع الشوارع التي تم أخذ عينات منها وجيرانها. ## يجب أن تكون التحديدات ذات الترتيب الأعلى ممكنة باستخدام منطق findMoreNeighbours ## نفس لكن استبدال العينة (الإدخال) بمخرجات من ## findFirstNeighbours def findFirstNeighbours (st2neigh، sample): compSts = {} for samp in sample.iterkeys (): for rSt في العينة [samp]: إذا لم يكن rSt في compSts: compSts [rSt] = [] لـ compSt في st2neigh [rSt]: compSts [rSt]. compSts: لـ st in compSts [aSt]: لـ nSt في st2neigh [st]: if nSt ليس في compSts [aSt]: compSts [aSt] .append (nSt) moreNeighs = compSts إرجاع المزيدالنصف ######### ############ ## The nHoods #################### samp = selectSample (seg2st، 1) n1 = findFirstNeighbours (st2neigh ، samp) n2 = findMoreNeighbours (st2neigh، n1) n3 = findMoreNeighbours (st2neigh، n2) ##################### ## تحقق من النتائج ###### ############### def checkResults (NeList): cntr = {} for c in neighList.iterkeys (): cntr [c] = 0 في قائمة الجيران [c]: cntr [ c] + = 1 عودة cntr ## هناك خطأ لا يوجد str eets ** يجب أن يكون ** بها أكثر من 2000 طلب جيران c1 = checkResults (n1) c2 = checkResults (n2) c3 = checkResults (n3)

يساعد!


هذا أبسط مما يبدو ، بشرط أن تستخدم بنية بيانات فعالة. واحد يعمل بشكل جيد هو قائمة انتظار (الشارع ، الترتيب ، {قائمة الجيران}). الخوارزمية هي:

بدء جميع الطلبات إلى المفقودين. اضبط ترتيب الشارع على 0. صف الشارع. بينما قائمة الانتظار غير فارغة {قم بإزالة شارع S من قائمة الانتظار. لكل جار لـ S {إذا كان ترتيب الجيران مفقودًا {عيِّن ترتيب الجيران على 1 + ترتيب S Queue the المجاور}}

قوائم الانتظار سهلة التنفيذ. في هذه الحالة ، إذا كان لديك مجموعة أ من (الشارع ، الترتيب ، الجيران) ، يمكن أن تكون قائمة الانتظار بسيطة مثل زوج من الفهارس ك, ل إلى أ. يبدأ كلاهما مهيأ إلى -1 (للفهرسة التي تبدأ عند 0). لوضع عضو من المصفوفة في قائمة الانتظار ، قل A [i] ، زيادة ل ومبادلة الإدخالات أنا و ل. لإزالة رأس قائمة الانتظار ، تحقق من أن قائمة الانتظار غير فارغة وإذا كانت كذلك ، قم بزيادة ك وقراءة أ [ك]. قائمة الانتظار فارغة في أي وقت ك أكبر من أو يساوي ل. بعد انتهاء الخوارزمية ، ربما تم تبديل عناصر المصفوفة وحُسبت أوامرها.

يجب أن تكون قادرًا على معالجة ملايين الشوارع في الثانية.


شاهد الفيديو: جيران الشبكة - تعرف على هذه الميزة الرائعة