نوع الجاذبية: هل هذا ممكن برمجيا؟ [مغلق

Question

لقد كنت أفكر مؤخرًا في استخدام التصميم الموجهة للكائن في خوارزمية الفرز. ومع ذلك ، لم أتمكن من إيجاد طريقة مناسبة للاقتراب في جعل خوارزمية الفرز هذه التي تقوم بالفرز في وقت O (n).

حسنًا ، هذا ما كنت أفكر فيه لمدة أسبوع. لدي مجموعة من بيانات الإدخال. سأقوم بتعيين كتلة لكل من بيانات الإدخال (افترض بيانات الإدخال نوع من Mass ونوع من Sphere. إذا افترضنا أن تكون جميع الأشياء كائنات كروية تمامًا ذات أشكال تتناسب مع كتلتها ، فإن أثقل واحد يمس الأرض أولاً.). سأضع جميع بيانات الإدخال الخاصة بي في المسافة في نفس المسافة من الأرض. وسأجعلهم يسقطون حرا. وفقا لقانون الجاذبية ، فإن أثقل واحد يضرب الأرض أولاً. والترتيب الذي يضربون سوف يعطيني البيانات المرتبة. هذا أمر مضحك بطريقة ما ، لكن تحت أشعر أنه يجب أن يكون ذلك ممكنًا باستخدام OO الذي تعلمته حتى الآن

هل من الممكن حقًا إنشاء تقنية فرز تستخدم جاذبية السحب مثل السيناريو أم أنا غبي/مجنون؟

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

Answer 1

الشيء هو ، على الرغم من واحد من الأفكار قد يكون من OOP تصميم العالم الحقيقي ، وهذا لا يعني أن هناك مراسلات مباشرة بين المدة التي يستغرقها شيء ما في العالم الحقيقي والمدة التي يستغرقها محاكاة الكمبيوتر.

تخيل الخطوات الفعلية المطلوبة لإجراءك:

1. يجب بناء كائن لكل عنصر في مجموعة البيانات الخاصة بك. على معظم الأجهزة الحديثة ، سيتطلب هذا وحده التكرار وبالتالي سيجعل استراتيجيتك o (n) في الأفضل.
2. يجب محاكاة تأثير الجاذبية ، لكل كائن. مرة أخرى ، فإن الطريقة الأكثر وضوحًا والمباشرة لتنفيذ هذا ستكون للتكرار.
3. يجب التقاط الوقت الذي يهبط فيه كل كائن على سطح "الأرض" في نموذج البرمجة الخاص بك ، وعبر بعض الآلية الخاصة بالتنفيذ ، يجب إدراج الكائن المقابل في قائمة مرتبة نتيجة لذلك.

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

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

Answer 2

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

Answer 3

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

Answer 4

الفرز للأغراض العامة هو في أحسن الأحوال O (n log n). لتحسين هذا ، عليك أن تعرف شيئًا عن البيانات بخلاف كيفية مقارنة القيم.

إذا كانت القيم كلها أرقام ، فرز Radix يعطي o (n) على افتراض أن لديك حدود علوية وأسفل للأرقام. يمكن تمديد هذا النهج للتعامل مع أي رقم - وفي النهاية ، يتم تمثيل جميع البيانات الموجودة في الكمبيوتر باستخدام الأرقام. على سبيل المثال ، يمكنك Radix-Sort Strings ، في كل تمريرة ، بالفرز حسب حرف واحد كما لو كان رقمًا.

لسوء الحظ ، فإن التعامل مع أحجام البيانات المتغيرة يعني إجراء عدد متغير من التمريرات من خلال نوع Radix. ينتهي بك الأمر بـ O (n log m) حيث M هي أكبر قيمة (نظرًا لأن Bits يمنحك قيمة تصل إلى (2^k) -1 لـ غير موقعة ، نصف الموقعة). على سبيل المثال ، إذا كنت تقوم بفرز الأعداد الصحيحة من 0 إلى M -1 ، حسنًا - لقد حصلت بالفعل على O (n log n) مرة أخرى.

يمكن أن تكون ترجمة مشكلة إلى أخرى طريقة جيدة للغاية ، ولكن في بعض الأحيان تكون مجرد إضافة طبقة أخرى من التعقيد والنفقات العامة.

Answer 5

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

Answer 6

في "الكمبيوتر الجاذبية" ، سيستغرق حل هذا النوع من الفرز O (1). ولكن مع وجود أجهزة الكمبيوتر الحقيقية كما نعرفها ، فإن فكرك الجانبي لن يساعد.

Answer 7

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

تعديل: يصيح. نسيت الفيزياء 101. بالطبع سوف يضربون جميعا في نفس الوقت. قون

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

Answer 8

تجاهل جميع العيوب التي ذكرها أي شخص آخر ، وهذا يتلخص بشكل أساسي في O(n^2) الخوارزمية ، لا O(n). يجب أن تتكرر على جميع "المجالات" ، والعثور على "أثقل" أو "أكبر" ، ثم ادفعها إلى قائمة ، ثم شطفها وكررها. أي للعثور على الأرض التي تضرب الأرض أولاً ، يجب عليك التكرار على القائمة بأكملها ، إذا كانت الأخيرة ، فسوف تأخذ O(n) الوقت ، يمكن أن يأخذ الثاني O(n-1), ، إلخ ... ولكن أسوأ من ذلك ، عليك أن تنفذ مجموعة من العمليات الرياضية في كل مرة فقط لحساب قيمة "وقت" عديمة الفائدة عندما تكون قد تكون قد تم فرزها على القيمة التي كنت مهتمًا بها في المقام الأول.

Answer 9

هممم. نوع الجاذبية.

إن تجاهل نموذج الجاذبية الخاص بك أمر خاطئ ، دعنا نرى أين تأخذنا هذه الفكرة.

الواقع المادي لديه 10^80 معالجات.

من المعروف أن الحدود السفلية الفعلية من الفرز هي سجل (n) إذا كان لديك معالجات N/2 لفرز كائنات N.

إذا كان لديك العديد من نوى وحدة المعالجة المركزية المتاحة ، فلا يوجد سبب لا يمكنك تشغيل Mergesort على عدة مؤشرات ترابط.

Answer 10

هناك في الواقع خوارزمية فرز مشهورة جدًا تسمى Spaghetti Sort والتي تشبه نوعًا ما لك. يمكنك الاطلاع على بعض التحليلات العديدة الخاصة به على الويب. على سبيل المثال cstheory.

Answer 11

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

Answer 12

أنا أحب الفكرة! إنه ذكي. بينما نعم ما يقوله الآخرون على العموم صحي المقارنة القائمة عارضات ازياء. ما تقترحه هنا هو نموذج مختلف تمامًا ، فهو يستحق المزيد من التفكير.

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

يتطلب المزيد من التفكير ، لكن فكرتك حادة!

(تحرير) الآن بالنظر إلى فكرة Enrique's Phys2d ، أعتقد أنها أكثر منطقية.

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

Answer 13

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

لا داعي للقلق أيضًا بشأن التسارع مع مرور الوقت ... نظرًا لأنك لا تهتم مدى السرعة التي تسير بها أو فيزياء واقعية ، يمكنك منحهم جميع السرعة الأولية X ، والانتقال من هناك.

تكمن المشكلة في ذلك أننا قمنا فقط بإعادة صياغة المشكلة وحلناها مثل هذا (الكود الكاذب):

int[] sortedArray; // empty
int[] unsortedArray; // full of stuff
int iVal = MAX_INT_VALUE;
while (true)
{
    foreach (currentArrayValue in sortedArray)
    {
        if (iVal = current array value
        {
            put it in my sortedArray
            remove the value from my unsortedArray
        }
    }
    if (unsortedArray is empty)
    {
        break;  // from while loop
    } 
    iVal--
}

المشكلة هي أنه لتشغيل محرك الفيزياء ، عليك التكرار عبر كل وحدة زمنية ، وسيكون ذلك O (1) ... مع أ جداً ثابت كبير ... العدد الثابت لقيم الدلتا التي سيعمل عليها النظام. العيب هو أنه بالنسبة للغالبية العظمى من قيم الدلتا هذه ، لن تقترب بشكل أساسي سوف ضرب.

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

Answer 14

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

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

حسنًا ، لذلك سترغب في محاكاة ذلك.

نأخذ طول مجالك L=1. مع حجم الخطوة ∆t كل منك N الكائنات تحرك طول vᵢ∙∆t في الوقت. هذا يعني أن كل كائن يحتاج sᵢ = L / (vᵢ∙∆t) خطوات قبل الوصول إلى النهاية.

النقطة الآن ، من أجل التمييز بين كائنين بسرعات قريبة جدًا ، ستحتاج إلى أن يكون لديك حجم خطوة مختلف لجميع كائناتك.

الآن ، في الأفضل الحالة ، هذا يعني أن الكائن 1 ينتهي في خطوة واحدة ، الكائن 2 في اثنين وما إلى ذلك. لذلك ، إجمالي عدد الخطوات هو S = 1 + 2 + … + N = N∙(N + 1)/2. هذا من النظام N∙N.

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

Answer 15

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

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

فكرة رائعة مع ذلك.

أيضا ، أحب فيديو فرز العملة التي نشرتها @jeremy. وأخيراً ، سيكون التوجه إلى أقل مخاوفي في بناء مثل هذا الجهاز. التفكير أكثر في الأمر ، ها هي سنتان غبيين على بناء مثل هذا الجهاز:

O 0 o O o

. . . . .
. . . . .
. . . . .
= = = = =

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

Answer 16

من إجابة هولسكي:

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

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

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

على افتراض أن المحاكاة تحدث في خطوات زمنية منفصلة أي إطارات, ، في كل إطار ، ستكون المسافة الجديدة لكل كائن: d = d - v وسيتم إضافة كائن إلى القائمة عندما يكون ذلك d ≤ 0. هذا هو الطرح واحد وشرط واحد. خطوتين منفصلتان لكل كائن ، لذلك يبدو أن الحسابات هي O (n): خطية.

الصيد هو ، إنه خطي ل إطار واحد فقط! يتضاعف بعدد الإطارات f مطلوب لإنهاء. المحاكاة نفسها هي O (NF): التربيعية.

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

يمكننا تحسين هذا عن طريق تحويله إلى خوارزمية متكررة+متكررة. في الكود البشري سيكون:

function: FESort: arguments: OriginalList, Tolerance
  define an empty local list: ResultList

  while OriginalList has elements
    define an empty local list: FinishedList
    iterate through OriginalList
      decrement the distance of each object by Tolerance
      if distance is less than or equal to zero, move object from OriginalList to FinishedList

    check the number of elements in FinishedList
      when zero
        set Tolerance to double Tolerance
      when one
        append the only element in FinishedList to ResultList
      when more
        append the result of FESort with FinishedList and half Tolerance to ResultList

  return ResultList

أتساءل عما إذا كان هناك أي تطبيق حقيقي مماثل يعمل لشخص ما.

موضوع مثير للاهتمام بالفعل :)

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

Answer 17

قبل بضعة أسابيع كنت أفكر في نفس الشيء.

فكرت في استخدام Phys2d مكتبة لتنفيذها. قد لا يكون عمليًا ولكن للمتعة فقط. يمكنك أيضًا تعيين أوزان سلبية للكائنات لتمثيل الأرقام السلبية. مع مكتبة Phys2d ، يمكنك تحديد الجاذبية بحيث ستذهب الكائنات ذات الوزن السلبي إلى السقف وستسقط الكائنات ذات الوزن الإيجابي. ثم ترتيب جميع الكائنات في الوسط بين الأرض والسقف مع نفس المسافة بين الأرضية والسقف. لنفترض أن لديك صفيفًا ناتجًا R [] من الطول = عدد الكائنات. ثم في كل مرة يلمس فيها كائن السقف الذي تضيفه في بداية الصفيف r [0] وزيادة العداد ، في المرة القادمة التي يلمس فيها كائن السقف الذي تضيفه عند r [1] ، في كل مرة يصل فيها كائن إلى الأرض أضفه في نهاية المصفوفة r [R.Length-1] ، في المرة القادمة التي تضيفها على R [R.Length-2]. في الكائنات النهائية التي لم تتحرك (بقيت عائمة في الوسط) يمكن إضافة في منتصف الصفيف (هذه الكائنات هي 0).

هذا ليس فعالًا ولكنه يمكن أن يساعدك في تنفيذ فكرتك.

Answer 18

1. أعتقد أنه من الجيد ذكر/الرجوع إلى: ما هي العلاقة بين P مقابل NP وقدرة الطبيعة على حل مشاكل NP بكفاءة؟الفرز O(nlog(n)), لماذا لا تحاول حل مشاكل NP-Hard؟
2. بموجب قوانين الفيزياء التي تسقط مع نسب إلىثابت الجاذبية الكتلة ضئيلة.
3. يمكن أن تؤثر محاكاة العملية الفيزيائية على التعقيد الفعلي للوقت.

Answer 19

تحليل: (1) تتم محاذاة جميع مراكز المجالات في البداية (2) عدد أكبر ==> كتلة أعلى ==> نصف قطرها أكبر ==> المسافة إلى الأرض السفلية (3) في "نفس التسارع" = نفس التطور السرعة = تطور السرعة نفسه = => نفس المسافة للمركز ==> كيف أكبر DE RADIUS ... كيف في وقت سابق سيضرب المجال الأرض ==> موافق مفاهيمي ، تقنية مادية جيدة إذا وصلت الكرة إلى الأرض ، يمكن أن ترسل إشارة مسافة بادئة + وقت ضرب ... سوف يعطي القائمة المصنفة عمليا ... ليست تقنية رقمية "جيدة"