التحقق من مساواة الأعداد الصحيحة:O(1) في C لكن O(log n) في Python 3؟

Question

خذ بعين الاعتبار هذه الوظائف المكافئة في C وPython 3.سيدعي معظم المطورين على الفور أن كلاهما كذلك $O(1)$.

def is_equal(a: int, b: int) -> bool:
  return a == b

int is_equal(int a, int b) {
  return a == b;
}

لكن فكر في ما يحدث تحت السطح.الأعداد الصحيحة هي مجرد سلاسل ثنائية، ولتحديد المساواة، ستقوم كلتا اللغتين بمقارنة السلاسل شيئًا فشيئًا.وفي كلتا الحالتين يكون هذا الفحص $O(ب)$ أين $ب$ هو عدد البتات.نظرًا لأن الأعداد الصحيحة لها حجم ثابت بالبتات في لغة C، فهذا ببساطة $O(1)$.

يحرر:C لا يقارن شيئا فشيئا انظر هذه الإجابة

ومع ذلك، في بايثون 3، الأعداد الصحيحة تفعل ذلك لا لها حجم ثابت ويبقى المسح $O(ب)$ لعدد البتات في الإدخال، أو $O(\سجل أ)$ أين $أ$ هي قيمة المدخلات في الأساس 10.

لذلك، إذا كنت تقوم بتحليل التعليمات البرمجية في بايثون، في أي وقت تقارن فيه عددين صحيحين، فإنك تشرع في رحلة معقدة بشكل مدهش $O(\log n)$ فيما يتعلق بالقيمة الأساسية 10 لأي من الرقمين.

بالنسبة لي هذا يثير عدة أسئلة:

1. هل هذا صحيح؟لم أر أي شخص آخر يدعي أن بايثون تقارن ints في وقت السجل.
2. في سياق إجراء المقابلة، هل يجب أن تلاحظ أو تهتم إذا كان المرشح يدعو ذلك $O(1)$?
3. هل يجب أن تلاحظ أو تهتم بهذا التمييز في العالم الحقيقي؟

يحرر:من السهل التحقق (والبديهي) من أن بايثون لا يمكنها مقارنة الأعداد الكبيرة بشكل تعسفي في وقت ثابت.لذا فإن أفضل طريقة لطرح السؤال 1 أعلاه قد تكون "ما هو (إن وجد) مبرر استدعاء هذه العملية $O(1)$؟لأنه عملي؟عادي؟ضمنا من قبل نموذج ذاكرة الوصول العشوائي؟

Answer 1

TL;DR:هناك CS الاتفاقية واصفا هذا النوع من العمليات كما $O(1)$ الذي يحدث كسر في الحالات القصوى لبيثون.هذه الحالات هي للغاية نادر جدا لكسر مع الاتفاقية من $O(1)$ وقد السلبية فائدة.هذا النوع من البراغماتية أمر طبيعي في الكبير $O$.

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

هل هذا صحيح ؟ أنا لم أر أي شخص آخر يدعي أن الثعبان يقارن رجات في سجل الوقت.

هذا هو المستغرب دقة.فمن صحيح أن الثعبان يقارن كبيرة جدا رجات في $O(\log n)$ وقت التشغيل.ولكن هل هو الصحيح لوصف هذه العملية $O(\log n)$?

في النهاية أنا مقتنع بهذه تأخذ من @TomvanderZanden:

إذا قال لك ج أو الثعبان النسخة $O(1)$ أي المقابلة يجب أن تكون سعيدة تماما.إذا قال ذلك (Python version) كان $O(\log n)$ أنها على الأرجح سيكون سعيدا ولكن أعتقد أنت أكثر شخص متحذلق الذين لا يتبعون العادي الاتفاقيات.

و

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

ومع ذلك أنا لا نقبل أن الجواب لأنني أعتقد أن الفقرة الأولى حاليا مضللة (سعيد للتغيير).

في نهاية المطاف هذه الحجة واقعية.قبل تعريف دقيق كبيرة $O$ بيثون الباحث المقارنة لا يزال على نحو يمكن التحقق منه $O(\log n)$.ولكن ليس من المفيد أن تعامل على هذا النحو ، لذلك يجب أن لا.وأود أن أضيف أن تكون صارمة كبيرة $O$ هو أن يغيب نقطة كبيرة $O$ تحليل.

Answer 2

الأعداد الصحيحة هي مجرد سلاسل ثنائية، ولتحديد المساواة، ستقوم كلتا اللغتين بمقارنة السلاسل شيئًا فشيئًا.

ليس تماما.ج intتكون s بحجم كلمة الآلة ويتم مقارنتها بتعليمات آلة واحدة؛بايثون intيتم تمثيل s في القاعدة $2^{30}$ (انظر على سبيل المثال https://rushter.com/blog/python-integer-implementation/) ومقارنتها رقمًا برقم في تلك القاعدة.وبالتالي فإن القاعدة ذات الصلة للوغاريتم هي $2^{30}$.

لو مرة على الأقل من الأرقام يمكن أن يحدها $2^{30د}$ ل أي مُثَبَّت $د$, ، المقارنة هي $O(1)$ (لأنه يتم مقارنة عدد الأرقام أولا)، وإذا لم يكن ذلك ممكنا، فمن المرجح أن تكون العمليات الأخرى أكثر إثارة للقلق من مقارنة المساواة.لذلك من الناحية العملية، أود أن أقول إنه من غير المرجح أن يكون الأمر مهمًا، وإذا كان الأمر كذلك فسوف تعرف (وسوف تستخدم لا intولكن شيء من هذا القبيل مكتبة جنو للحسابات الدقيقة المتعددة في ج أيضاً).

Answer 3

يتم تعريف

التعقيد بالنسبة لطراز حساب.P و NP، على سبيل المثال، يتم تعريفها من حيث آلات Turing.

للمقارنة، والنظر في نموذج Word RAM.في هذا النموذج، تنقسم الذاكرة إلى كلمات، يمكن الوصول إلى الكلمات في وقت ثابت، ويمكن تمثيل حجم المشكلة باستخدام $ O (1) $ الكلمات.

لذلك، على سبيل المثال، عند تحليل عملية الفرز القائم على المقارنة، نفترض أن عدد العناصر يمكن تخزين $ N $ في $ o (1) $ الكلمات، لذلك يستغرق وقتا ثابتا لقراءة أو كتابة رقم بين $ 1 $ و $ n $ .

Answer 4

هل هذا صحيح؟ أنا لم أر أي شخص آخر يدعي أن بيثون يقارن Ints في وقت السجل.

لا (وقليل نعم). ضع في اعتبارك المطالبة الإثارة الفكرية التالية (ولكن ليس صحيحا حقا): يمكن أن يكون لدى الكمبيوتر فقط كمية محدودة من الذاكرة (يحدها عدد الذرات في الكون)، وبالتالي فإن إصدار Python هو أيضا $ O (1) $ .

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

افترض أنني طلب منكم تحليل خوارزمية الفرز المكتوبة في C. قد تذكر أنه يستخدم Ints لفهرسة الصفيف، لذلك يمكن أن فرز مجموعة من الحجم فقط من حجم 2 دولار ^ {31} -1 $ . ومع ذلك، عندما نحلل مثل هذه القطعة من التعليمات البرمجية، نتظاهر بأنه يمكن أن يتعامل مع صفائف كبيرة بشكل تعسفي. من الواضح أننا لا نقول تقارن عدد صحيح C $ O (1) $ (1) $ لأن يمكنه فقط معالجة أرقام 32 بت فقط.

في سياق إجراء مقابلة، هل يجب أن تلاحظ أو يهتم إذا يدعو المرشح إلى هذا O (1)؟

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

سيكون بشكل لا يصدق Pedantic إذا اشتكفت برنامج C الخاص بك غير صحيح لأنه يمكن أن يحسب فقط إلى $ 2 ^ ^ {} -1 $ .

نحن نفترض عموما أن الأرقام صغيرة بما يكفي بحيث يمكنها تتوافق داخل كلمة واحدة / عدد صحيح. نحن نفترض إضافة (أو أي عملية أخرى) في $ O (1) $ (1) $ ، لأنه سيكون مزعجا للغاية يجب أن تكتب $ o (\ log n) $ في كل مكان، وسوف تجعل كل شيء غير قابل للقراءة على الرغم من $ \ log n $ هو صغير جدا لا يهم حقا على أي حال.

إذا قلت إصدار C أو Python كان $ O (1) $ يجب أن يكون أي مقابلة سعيدا تماما. إذا قلت ذلك (إصدار بيثون) كان $ o (\ log n) $ ربما لا يزالون سعداء، ولكن يعتقدون أنك شخص محري للغاية لا " اتبع الاتفاقيات العادية.

يجب أن تلاحظ أو يهتم بهذا التمييز في العالم الحقيقي؟

نعم! إنه يبدأ الأمر عندما تصبح الأرقام كبيرة جدا افتراض أنها صغيرة تنتهك. دعنا نقول أنك تقابل جوجل وطلب منك حساب عدد استفسارات البحث التي قام بها مستخدمي الإناث في العام الماضي. سيتم تبرير القائم بإجراء المقابلة شكرا إذا كتبت برنامجا جايا باستخدام Ints.

يمكنك التبديل إلى استخدام أوقات طويلة وما زالت مبررة في الاتصال به $ O (1) $ (1) $ ، وبالمثل، استدعاء إصدار Python $ O (1) $ مبرر أيضا. $ O (1) $ v.s.. $ o (\ log n) $ شيء يبدأ فقط في المسألة عندما تصبح الأرقام طويلة جدا. على سبيل المثال، إذا كانت مهمتك هي كتابة برنامج يحسب أرقام $ \ Pi $ أو بعض المهمة المشابهة. إذا كتبت برنامج بيثون لهذه المهمة، لم يذكر خصوصيات التعقيد عندما سئل، فإن المقابلة سوف يهتم.

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

متى يجب أن تهتم؟

حتى الآن، لقد كنت غامضا قليلا عن الأرقام "الكبيرة" و "صغيرة". في نموذج RAM شائع الاستخدام، يسمح لك بتفترض أن العمليات العددية التي يمكن القيام بها في $ O (1) $ على الأرقام التي تحتوي على معظم $ o (\ log n) $ بت (حيث $ n $ هو طول الإدخال). مبرر هذا الافتراض هو أنه إذا كان لدينا مدخلات الطول $ n $ ، يجب أن تكون المؤشرات / المؤشرات في لغتها البرمجة طويلة بما يكفي لتكون قادرة على معالجة مساحة الإدخال بأكملها. لذلك، في نموذج ذاكرة الوصول العشوائي، إذا كان الإدخال رقم ثنائي من $ n $ (binary)، فإن تعقيد التحقق من المساواة هو $ o (\ frac {n} {n} {\ log n}) $ نظرا لأنه يمكننا التحقق من تكافؤ مجموعة واحدة من $ o (\ log n) $ < / span> بت في واحدة $ O (1) $ العملية.

Answer 5

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

بالقياس، خذ بعين الاعتبار الدالة C int is_equal(char a, char b) { return a == b; } ووظيفة بايثون def is_equal(a: str, b: str) -> bool: return a == b.أصبح من الواضح الآن أن الوظائف ليست متكافئة، ولكن السبب وراء ذلك هو تمامًا نفس السبب الذي يجعل وظائفك غير متكافئة.نتوقع فقط رؤية سلاسل ضخمة في بايثون طوال الوقت، لكننا لا نتوقع حقًا وجود سلاسل ضخمة على الرغم من أننا نعلم بالطبع أنها ممكنة.لذلك، نتجاهل في معظم الأحيان حقيقة أن الأعداد الصحيحة في بايثون كبيرة، ونقوم بتحليلها كما لو كانت ذات حجم ثابت.في الحالات النادرة التي نهتم فيها بتوقيت عمليات البيغنوم، يمكنك استخدام التعقيدات "الحقيقية".وبالطبع، استخدم أيضًا GMP في كود C الخاص بك.

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

في بعض الحالات، يمكنك إضفاء الطابع الرسمي على هذا (إذا كنت بحاجة إلى ذلك حقًا) بالقول إنك تقصر تحليلك على الأعداد الصحيحة الصغيرة.بعد ذلك، قد تفكر في مدى تعقيد بعض الخوارزميات من حيث حجم بعض مصفوفات الأعداد الصحيحة، ومعاملة جميع العمليات الحسابية على أنها O(1).إذا كنت تفكر في خوارزميات خطية حقًا أو أسوأ من حيث حجم العدد الصحيح، فيمكنك إضفاء الطابع الرسمي عليها بالقول إنك ستتجاهل عامل السجل، نظرًا لأن كل ما يهمك حقًا هو ما إذا كان التعقيد أقرب إلى خطية أو تربيعية، لأن O(n log n) جيدة مثل الخطية لأغراضك.ومع ذلك، في كل الأوقات تقريبًا، لا تحتاج إلى إضفاء الطابع الرسمي على تعقيد الخوارزميات في بايثون.إذا وصلت إلى نقطة تحديد لغة برمجة، فأنت لم تعد تمارس علوم الكمبيوتر المجردة بعد الآن؛-)

في سياق إجراء مقابلة ، إذا لاحظت أو تهتم إذا استدعى المرشح هذا $O(1)$?

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

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

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

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

Answer 6

هل هذا صحيح؟لم أر أي شخص آخر يدعي أن بايثون تقارن ints في وقت السجل.لدى بايثون بالفعل تنسيقًا صحيحًا دقيقًا.ومع ذلك، علينا إجراء مقارنة عادلة هنا.إذا نظرنا إلى المجموعة الفرعية من الأعداد الصحيحة الموجودة على حدود $[0,2^{64}]$, نجد أن عملية بايثون هي الزمن الثابت.

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

في سياق إجراء المقابلة، هل يجب أن تلاحظ أو تهتم إذا أطلق المرشح هذا الرقم O(1)؟

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

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

هل يجب أن تلاحظ أو تهتم بهذا التمييز في العالم الحقيقي؟

من الناحية العملية:لا.ليس حتى تواجهها تمامًا، وتصلح المشكلة في تصحيح الأخطاء.بايثون تفعل كثير من الأشياء "الآمنة بشكل عام" والفعالة للغاية.ولهذا السبب أصبحت واحدة من أكثر اللغات شعبية في العالم.

لحالة مماثلة:مدى سرعة x.y في بايثون؟نحن نفكر فيه على أنه O(1)، ولكن يوجد بالفعل بحث عن التجزئة هناك.يستخدم بحث التجزئة هذا آلية فحص معروفة، والبحث الناتج هو في الواقع O(n).لن ترى هذا أبدًا في الكود العادي.ولكن في التعليمات البرمجية التي يتمكن فيها الخصم من ملء قاموسك بمحتواه الخاص، يمكنه عمدًا إنشاء مفاتيح تتصادم بهذه الطريقة.

Answer 7

لم أصادوا أبدا نصا يعامل العمليات العددية "العادية" كأي شيء إلى جانب الوقت الثابت، مع الافتراض الضمني أن الحجم لديه بعض العلوي المحدود المعقول (على سبيل المثال 64 بت).ربما يكون الأمر أكثر دقة لنقل الافتراض، ولكن لجمهور CS، أعتقد أنه ضمني.

القيام بذلك من شأنه أن يقدم الكثير من التعقيد في مناقشات موضوعات غير ذات صلة أساسا.لا يتم تطبيق تطبيق BigInt عادة بت بعض الشيء، ولكن في Base- حجم الكلمة)، بحيث تكون المشكلة O (B)> O (1) تعبئ فقط بأعداد كبيرة رائعة.

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