سؤال معقد في المصفوفات

[فارس القبيلة]

السلام عليكم


لدي فكرة وارغب بتطبيقها ولكن وصلت لنقطه اوقفتني وهي في المصفوفات

$x=101;
$a=array(0,100,500,999,10002); 

مثلا المصفوفة بالاعلى فيها مجموعه عناصر وارغب باستخراج عنصر واحد بشرط معين

والشرط هو ان تكون قيمه العنصر اقرب قميه للمتغير اكس من ناحيه الاسفل

بمعنى انه عندما تكون قيمه اكس 99 يقوم الكود بارجاع القيمه صفر وعندما تكون قيمه اكس 1000 يقوم بارجاع القيمه 999



ولكن بدون استخدام الدوال التكراريه لانها تستهلك موارد المعالج اريد طريقه اخرى

[ff5006]

وعليكم السلام ,
أعجبني السؤال فحاولت التجربة و البحث عن جواب , الكود :

http://shafrah.com/code/v87zB4o

أو

http://shafrah.com/code/z7nFWxI

مقارب لما تبحث عنه.

[khashabawy]

<?php 


$arr = array(0, 5, 10, 11, 12, 20);

function getNearest($arr,$var){
    usort($arr, function($a,$b) use ($var){
        return  abs($a - $var) - abs($b - $var);
    });
    return array_shift($arr);
}


$var = 16;

echo getNearest($arr,$var);


?>

[Abdullah Alhoshan]

<?php
$x=99; 
$a=array(0,100,500,999,10002);  


function lowerValue($reslut,$number){    
global $x;        
if($x > $number){            
$reslut = $number;        
}    
return $reslut;
}

$b = array_reduce($a, "lowerValue");

print_r($b);

?>

[Cenrak]

و عليكم السلام.

هذا ليس "سؤال معقد في المصفوفات". هذا "سؤال مبتدئ في الخوارزميات". أنصحك تقرأ عن خوارزميات البحث. و العلم مهو عيب

السؤال في هذه الحالة: هل المصفوفة مرتبة؟
إذا المصفوفة مرتبة، الحل سهل. Binary Search. الخوارزمية هذه أسرع شئ لك. و أسرع من حلول الشباب هنا كلهم. في حالة المصفوفة كانت صغيرة، الحلول كلها متقاربة.

و عشان تصدقني انها أسرع، هذه تجربة لمصفوفة من 6666667 عنصر. استخدمت range(0,40000000,6) عشان انتجها. الرقم المدخل كان 99 و الناتج المتوقع 96.

طريقة ff5006 الأولى جابت الناتج صح و أخذت

real    0m6.230s
user    0m5.440s
sys     0m0.524s

طريقة خشباوي جابت الناتج غلط (102 بدلا من 96) و أخذت

real    1m57.705s
user    1m52.639s
sys     0m0.528s

طريقة عبدالله الهوشان جابت الناتج صح و أخذت

real    0m4.947s
user    0m4.432s
sys     0m0.292s

طريقة الـ Binary Search جابت الناتج صح و أخذت

real    0m1.702s
user    0m1.344s
sys     0m0.296s

و هذه شفرة التطبيق: http://shafrah.com/code/G2JSdmo

Binary Search بأصلها لا تحل مشكلتك. لأنها تبحث عن الرقم في المصفوفة. إذا وجدته ترجع قيمة الـ index، و ترجع -1 في حالة انه الرقم غير موجود. و عشان الـ Binary Search تحل مشكلتك، حطيت reduce عشان أقدر اطلع الـ index المناسب

هذا لا يعني إن تطبيقات الشباب غلط. لكن في حالة إذا المصفوفة مرتبة، فإن آخر حل افضل حل يمكن تحصل عليه.

بس إذا المصفوفة مش مرتبة، هنا يجي سؤال: هل تكلفة ايجاد الحل باستعمال طرق الشباب أقل تكلفة من ترتيب المصفوفة و من ثم تطبيق الـ binary search؟ انت و جوابك هوه اللي يقرر الحل الأنسب لك.

و على فكرة، ترتيب المصفوفة في الـ PHP يستعمل Quick Sort


تعديل:
قمت بإضافة متغير mid_number لتحسين الأداء قليلا. sh.af/DI7C4aw

ولكن بدون استخدام الدوال التكراريه لانها تستهلك موارد المعالج اريد طريقه اخرى

للأسف، لا يمكنك مهما صار تنفيذ المطلوب بدون دالة تكرارية. لكن ما يمكن فعله هو تقليل مرات التكرار. و هذا كان هدفي وقت استخدامي لـ Binary Search.

مثلا، إذا أردت استخدام sort($array)، تعرف إنها، خلف الكواليس، تستعمل الدوال التكرارية؟ إذا شاك في كلامي، حمّل الشفرة المصدرية للـ PHP. ابحث عن ملف اسمه array.c (تسهيلا، هذا هو http://sh.af/Cu5nEfY).

الشفرة لتنفيذ الـ sort على مصفوفة موجودة في سطر 536. يمكن تقول إن مافي أي دالة تكرارية. ردي: أول شرط في سطر 541 للتحقق من سلامة المدخلات.
ثاني شرط في سطر 547 فيه تنفيذ لدالة الـ sort باستخدام دالة zend_hash_sort و بخوارزمية zend_qsort.

دالة zend_hash_sort موجودة في ملف zend_hash.c (تسهيلا: http://sh.af/91XwZaw) في سطر 1421. بتلاحظ وجود دوال تكرارية

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

[khashabawy]

أعجبنى ردك الجميل أخى cenak


للعلم أن لم أكتب الحل . ولكنى نقلته من أحد المواقع محاولاً المساعده

و أنا معك أنه إستخدام foreach يحل الموضوع ولا يستهلك شئ يذكر

[Cenrak]

و أنا معك أنه إستخدام foreach يحل الموضوع ولا يستهلك شئ يذكر

لم استخدم الـ foreach في حل الـ Binary Search. استخدامه صحيح لكن مكلف من ناحية السرعة.

في علم الخوارزميات، الـ foreach تستهلك O(n) عملية بحث
طريقة الـ Binary Search تستهلك O(log2n)

بلغة الرياضيات، إذا المصفوفة فيها 1024 عنصر. في أسوأ الحالات، foreach تستهلك 1024 عملية بحث في أسوأ الحالات لإيجاد ما يريده فارس القبيلة
أما الـ Binary Search تستهلك 10 عمليات بحث في أسوأ الحالات لإيجاد الحل.

[khashabawy]

هذا حلى

<?php

$x=100000;
$a=array(0,100,500,999,10002); 

asort($a);

foreach($a as $key=>$num){

    if($x <= $num){
        
        if(!isset($wanted)){
            $wanted = $a[$key - 1];
        }

    }

}

if(!isset($wanted)){
     $wanted = $num;
}


echo $wanted;


?>

[Cenrak]

عبدالله، للأسف حلك ينقصه الكثير.

حلك ما زال مكلف (مع حذف سطر asort)، و هذا الوقت

real    0m2.569s
user    0m1.972s
sys    0m0.480s

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

هذا نفس حلك لكن تنفيذ الـ foreach يتوقف متى ما الرقم الموجود في المصفوفة أكبر من x، و هذا رابط الحل: http://sh.af/e5CH8OY

المشاكل حلولها سهلة بس يبغالها شوي تفكير

رائد

[Abdullah Alhoshan]

كان حل سريع .. السأل لم يفصل بشكل اكثر متطلباته .. هذا الموقع جيد ويعطيك نصائح على احسن طريقه لإعادة الصف .. http://www.sorting-algorithms.com