مابي، بيثون وشبكة

Question

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

def unweighted_random_walk(starting_point,ending_point, graph):
    '''
    starting_point: String that represents the starting point in the graph
    ending_point: String that represents the ending point in the graph
    graph: A NetworkX Graph object
    '''
    ##Begin the random walk
    current_point=starting_point
    #current_node=graph[current_point]
    current_point_neighors=graph.neighbors(current_point)
    hitting_time=0

    #Determine the hitting time to get to an arbitrary neighbor of the
    #starting point
    while current_point!=ending_point:
        #pick one of the edges out of the starting_node with equal probs
        possible_destination=current_point_neighbors[random.randint(0,current_point_neighors)]
        current_point=possible_destination
        current_point_neighbors=graph.neighbors(current_point)
        hitting_time+=1
    return hitting_time

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

سؤالي هو: هل هناك أي طريقة يمكنني استخدام HadoP MapReduce لتعزيز بعض العمليات التي تجري هنا لهذا المشي العشوائي؟ هل هناك طريقة أفضل بالنسبة لي أن أفعل المشي العشوائي الخاص بي؟

Answer 1

لمعالجة سؤالك:

1. تحتاج إلى معالجة تعليق NED. لقد ضربني قوله. شرح الكود الخاص بك؛ المزيد عن ذلك لاحقا.

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

3. على افتراض أن كل مشي عشوائي مستقل، ومع ذلك، أنت يمكن تشغيل العديد من المشي العشوائي في وقت واحد. نسمي هذا السيناريو بالتوازي بشكل محزن, وهذا شيء محظوظ جدا.

4. ليس لدي أي فكرة لماذا تريد استخدام Hadoop، وتحديدا هنا. يجب أن تكون الخطوة الأولى، "هل يمكنني كتابة هذا كبرنامج أساسي واستخدام برنامج نصي QSUB (أو ما يعادله) لزراعة مجموعة من أشواط هذا البرنامج إلى الخادم؟" إذا كانت الإجابة لا، فإن الخطوة التالية هي "هل يمكنني استخدام وحدة متعددة المعالجات؟ "إذا ذهبت مع multiprocessing، فقد ترغب في إلقاء نظرة على العرض التقديمي متعدد المعالجات ل Jesse Noller من Pycon 2009.

الآن، فيما يتعلق برمزك الخاص ...

1. تحتاج إلى شرح العقد في الرسم البياني الخاص بك هي. أنا مرتبك لماذا تعاملهم مثل القاموس (الدعوة .keys()) عليهم. إذا كانوا قواميس، أخبرنا ما هي المفاتيح والقيم. آمل أنك لا تخزن الجيران كمفاتيح هناك، لأن الشبكة تعطيك بالفعل ذلك، عبر Graph.neighbors() طريقة. إذا كنت تخزن جيران العقد في العقد أنفسهم، فلديك سوء فهم لمكتبة الشبكة. دع الرسم البياني يقوم بالعمل من أجلك.

2. لديك نفس المنطق مرتين في unweighted_random_walk(), ، مرة واحدة في الرحلة من العقدة البدء إلى العقدة الوجهة، ثم مرة أخرى للعقدة الوجهة إلى عقدة البدء. لماذا ا؟ كل ما تحتاجه هو المنطق لاتجاه واحد. استدعاء هذه الوظيفة مرتين. اتصل به مع العقد البدء والوجهة كحجية للحصول على الاتجاه بطريقة واحدة، ثم قم بتبديل ترتيب الحجج لتكون وجهة ثم تبدأ في الحصول على المشي في الاتجاه الآخر. عندئذ يكون لديك مكالمتين مستقلتين، ويمكن الآن تشغيلها بالتوازي.

3. لا تستخدم while True:- لا يوجد هنا فقط، ولكن بشكل عام. يجب أن تشير دائما إلى الشرط الفعلي الذي لم يستمر به. على سبيل المثال،

   while current_point != ending_point:
       ...
   

4. لا ترجع سلسلة من المعلومات، وإرجاع المعلومات مباشرة. على سبيل المثال،

   return hitting_time
   

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

أنظر أيضا

• ال مشروع ديسكو للحصول على تطبيق Python Accessable Map Reduce
• عرض Jesse Noller على التزامن والحوسبة الموزعة من PYCON 2009.

تعديل: وشملت روابط لتقديم عروض جيسي نولر والديسكو.

Answer 2

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

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

Answer 3

ليس عليك بالفعل إجراء المشي العشوائي إذا كنت تستخدم الصيغة مفصلة في هذه الورقة.