तो - क्या हाल ही में आपको "खोजा गया" रोमांचक एल्गोरिदम है?

Question

मुझे नए और चालाक एल्गोरिदम के बारे में पढ़ना पसंद है। और मुझे बॉक्स से बाहर निकलना पसंद है, इसलिए गणना के सभी क्षेत्रों के सभी प्रकार के एल्गोरिदम का स्वागत है।

समय-समय पर मैंने वर्तमान शोध के साथ अनुसंधान और मेरे क्षितिज का विस्तार करने के लिए शोध पत्र पढ़े। मैं भी नई चाल सीखना पसंद करता हूं। दुर्भाग्य से मैं केवल रुचि के अपने क्षेत्र पर ध्यान केंद्रित करता हूं, इसलिए मुझे बहुत उपयोगी चीजें याद आती हैं।

चलो मुख्यधारा की चीजें पोस्ट न करें। इसके बजाय कुछ खास लिखो जो आपको लगता है: "वाह - अब एक चालाक समाधान है!"।

Answer 1

यह कुछ नया या रोमांचक नहीं है, लेकिन मुझे Levenshtein Distance पसंद है।

Levenshtein दूरी अक्सर दोनों के बीच तार संपादित दूरी के रूप में भेजा है और मूल रूप से एक मीट्रिक कि आपरेशन के न्यूनतम संख्या की गणना करने के लिए अन्य एक स्ट्रिंग में कनवर्ट करने से दो तार के बीच अंतर का आकलन करता है।

मैं इस एल्गोरिदम का उपयोग कर रहा हूं ताकि बाहरी स्रोत (संभावित रूप से अलग) तारों के बाहरी स्रोत के क्रम से मेल खाने के लिए कई तारों की एक छंटाई का सुझाव दिया जा सके।

Answer 2

मैं कुछ भी उपयोग कर सकता हूं जो हर किसी का उपयोग कर सकता है: आत्मनिर्भर प्रकार। http://en.wikipedia.org/wiki/Introsort

एक नया प्रकार एल्गोरिदम जो त्वरित, सम्मिलन और ढेर प्रकार का सर्वोत्तम संयोजन जोड़ता है। सटीक होने के लिए यह स्वयं द्वारा एक नया एल्गोरिदम नहीं है लेकिन बहुत चालाक संयोजन है।

आपको उस बिंदु तक त्वरित-क्रम की गति मिलती है जहां त्वरित-क्रम degenerated O (n²) केस में चला जाता है। यह लगभग किसी भी कीमत के लिए पता चला है। शेष विभाजन ढेर का उपयोग करके सॉर्ट किया जाता है- या मर्ज-सॉर्ट। यह न केवल अपरिवर्तित मामले से बचाता है बल्कि स्टैक-उपयोग के लिए एक स्पष्ट परिभाषित ऊपरी बाउंड बनाता है।

सम्मिलन क्रम - सामान्य रूप से - त्वरित-प्रकार के पास से छोड़े गए सभी छोटे विभाजनों की देखभाल करता है।

मेरे लिए यह एक नई खोज थी क्योंकि मैंने अपने अनुप्रयोगों के लिए त्वरित-प्रकार का उपयोग करना बंद कर दिया था।

मैं एम्बेडेड डिवाइस पर बहुत काम करता हूं और मुझे स्टैक उपयोग की परवाह है। त्वरित-क्रम का उपयोग करना हमेशा थोड़ा जोखिम भरा था क्योंकि यह बेहोश मौका है कि यह ढेर पर अमोक चलाता है। भले ही आप जानते हैं कि वर्तमान डेटा के साथ सबकुछ ठीक होगा, आप कभी नहीं जानते कि किसी ने बाद में आपके कोड को एक अलग प्रोजेक्ट में नहीं डाला है और डेटा के लिए इसका उपयोग नहीं करता है।

आत्मनिर्भर प्रकार के लिए धन्यवाद अब मेरे पास स्टैक उपयोग पर पूर्ण नियंत्रण है और साथ ही साथ प्रदर्शन को बढ़ावा मिला है।

Answer 3

यहां Viterbi algorithm का कार्यान्वयन है जिसे मैंने हाल ही में "खोजा" है। यहां वीडियो उद्देश्य एन्कोडिंग में फ्रेम प्रकारों के इष्टतम वितरण का निर्णय लेना है। विटरबी स्वयं कभी-कभी समझने में थोड़ा मुश्किल होता है, इसलिए मुझे लगता है कि सबसे अच्छी विधि वास्तविक उदाहरण के माध्यम से है।

इस उदाहरण में, अधिकतम कॉन्सेक्टीव बी-फ्रेम 2 है। सभी पथ एक पी-फ्रेम के साथ समाप्त होना चाहिए।

1 की पथ लंबाई हमें P हमारे सर्वोत्तम पथ के रूप में देती है, क्योंकि सभी पथ एक पी-फ्रेम पर समाप्त होना चाहिए, कोई अन्य विकल्प नहीं है।

2 की पथ लंबाई हमें BP और _P देता है। "_" लंबाई 1 का सबसे अच्छा मार्ग है। यह हमें BP और PP देता है। अब, हम वास्तविक लागत की गणना करते हैं। मान लें, इस उदाहरण के लिए, बीपी सबसे अच्छा है।

पथ की लंबाई 3 हमें BBP और _B पी और __P देता है। "__" लंबाई 2 का सबसे अच्छा मार्ग है। यह हमें BBP और PBP और BPP देता है। अब, हम वास्तविक लागत की गणना करते हैं। मान लें, इस उदाहरण के लिए, कि बीबीपी सबसे अच्छा है।

4 की पथ लंबाई हमें _BBP और __BP और ___P देता है। "___" लंबाई 3 का सबसे अच्छा मार्ग है। यह हमें पीबीबीपी और बीपीबीपी और बीबीपीपी देता है। अब, हम वास्तविक लागत की गणना करते हैं। मान लें, इस उदाहरण के लिए, कि बीपीबीपी सबसे अच्छा है।

4 की पथ लंबाई हमें __BBP और ___BP और ____P देता है। "____" लंबाई 4 का सबसे अच्छा मार्ग है। यह हमें BPBBP और BBPBP और BPBPP देता है।

अब - एक मिनट प्रतीक्षा करें - सभी पथ सहमत हैं कि पहला फ्रेम B है! तो पहला फ्रेम B है।

प्रक्रिया तब तक दोहराई जाती है जब तक वे सहमत न हों कि कौन सी फ्रेम पहले पी-फ्रेम है, और फिर एन्कोडिंग शुरू होती है।

यह एल्गोरिदम कई क्षेत्रों में समस्याओं की एक बड़ी विविधता के लिए अनुकूलित किया जा सकता है; यह भी वही एल्गोरिदम है जिसे मैंने this post में संदर्भित किया है।

Answer 4

मैंने हाल ही में पूर्णांकेंट वर्ग जड़ों के लिए पुराने मार्चेंट कैलकुलेटर एल्गोरिदम का एक बाइनरी संस्करण पुनः खोज लिया। कोई गुणा या विभाजन नहीं, केवल जोड़, घटाव, और बदलाव। मुझे खेद है, मैंने संदर्भ खो दिया:

def assert 
    raise "Assertion failed !" if $DEBUG and not yield 
end 

def sqrt(v) 
    value = v.abs 
    residue = value 
    root = 0 
    onebit = 1 
    onebit <<= 8 while (onebit < residue) 
    onebit >>= 2 while (onebit > residue) 
    while (onebit > 0) 
     x = root + onebit 
     if (residue >= x) then 
      residue -= x 
      root = x + onebit 
     end 
     root >>= 1 
     onebit >>= 2 
    end 
    assert {value == (root**2+residue)} 
    assert {value < ((root+1)**2)} 
    return [root,residue] 
end 

$DEBUG = true 

a = sqrt(4141290379431273280) 
puts a.inspect 

दुर्भाग्य से, यह कहना भूल गया कि यह रूबी है, उन अपरिचित लोगों के लिए।

Answer 5

जब मैं डेटा संपीड़न के लिए Burrows-Wheeler block sorting algorithm (bzip2 में उपयोग किया गया) के बारे में सीखा तो मुझे प्रभावित हुआ। आश्चर्य की बात यह है कि सॉर्टिंग चरण उलटा है!

Answer 6

मैंने हमेशा सोचा कि magic square-root क्वैक में कार्य बहुत चालाक थे। यह बहुत तेजी से होता है, क्योंकि यह इस तरह के विभाजन आदि

float SquareRootFloat(float num) { 
    long i; 
    float x, y; 
    const float f = 1.5F; 

    x = num * 0.5F; 
    y = num; 
    i = * (long *) &y; 
    i = 0x5f3759df - (i >> 1); 
    y = * (float *) &i; 
    y = y * (f - (x * y * y)); 
    y = y * (f - (x * y * y)); 
    return num * y; 
} 

उन्होंने यह भी एक संबंधित magic inverse square-root है के रूप में धीमी आपरेशन के किसी भी बचा जाता है।

Answer 7

मुझे यह बहुत उपयोगी सबूत मिला कि एक^एन = बी^एन + सी^एन लेकिन केवल एन = 2 के लिए।
दुर्भाग्य से यह टिप्पणी बॉक्स इसे रखने के लिए बहुत छोटा है!

Answer 8

बायोइनफॉरमैटिक्स अजीब रूपों में डेटा के भार उत्पन्न करने वाले प्रयोगों के मामलों से भरा है जो कल्पना करने के लिए कल्पनाशील एल्गोरिदम की आवश्यकता होती है।

an introduction to bioinformatics algorithms सामान के इस तरह के एक महान पढ़ा है

Answer 9

यह दूसरों के रूप में के रूप में आकर्षक नहीं है, लेकिन यह काम में आया था:

((m+n) + (m-n))/2 === m (for any two real numbers m and n)

मैं एसक्यूएल में कुछ कुल क्वेरी तर्क उपयोग कर रहा था किसी आइटम की रेटिंग गिनने के लिए। रेटिंग या तो +1 और -1 हैं। मुझे सकारात्मक रेटिंग (एम) की संख्या जानने की जरूरत थी, केवल रेटिंग की कुल संख्या, और उनकी राशि।

इस तर्क का उपयोग करके वास्तव में क्वेरी को बढ़ा दिया और मुझे 0 रेटिंग वाले आइटम के लिए परिणाम वापस करने की अनुमति दी।

(मैं +1 और -1 चुनें नहीं था, मुझे लगता है कि विरासत में मिला।)

Answer 10

Dynamic programmingoptimal control problems के साथ अपने सभी बिजली लेता है। बहुत ताज़ा