क्यों जंग एक कार्यात्मक प्रोग्रामिंग भाषा बन जाना चाहिए

नमस्कार, हेब्र!

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

1. अनिवार्य कार्यान्वयन के लिए - जंग से लाभ केवल 20% था। इसका मतलब है कि जेवीएम मूल प्रदर्शन के करीब आ गया है, और इसमें सुधार के लिए कुछ भी नहीं बचा है।
2. एक कार्यात्मक कार्यान्वयन के लिए, रस्ट 4.5 गुना तेज हो गया, मेमोरी की खपत 5.5 गुना कम हो गई, और एक कचरा कलेक्टर की अनुपस्थिति ने कार्यक्रम को और अधिक स्थिर बना दिया (प्रदर्शन में कम भिन्नता)। यह उन लोगों के लिए दिलचस्प है जो तेज कार्यात्मक कार्यक्रम लिखना चाहते हैं।
3. डेटा के एकमात्र मालिक की अवधारणा (और केवल उत्परिवर्तित संदर्भ) रस्ट में अपनाई गई अवधारणा, अपरिवर्तनीयता की अवधारणा से बहुत मिलती-जुलती है, जिसके परिणामस्वरूप कार्यात्मक एल्गोरिथम, अपरिवर्तनीयता, पुनरावृत्ति और प्रतिलिपि बनाने के आधार पर आसानी से लगभग कोई पुनर्लेखन नहीं होता है, जबकि अनिवार्य एल्गोरिदम कोड को फिर से डिज़ाइन करने के लिए मजबूर करते हैं। लिंक उत्परिवर्तन, जीवनकाल आदि पर विचार करें।

निष्कर्ष - एफपी के लिए जंग विशेष रूप से बनाई गई है, हालांकि इसके सिंटैक्स की संभावनाएं अभी तक स्काला तक नहीं पहुंची हैं।

तो, आइए स्काला के साथ शुरू करते हैं और 2 शैलियों में त्वरित छँटाई को लागू करते हैं:

अभेद्य रूप से - हम एक ही सरणी का उपयोग करते हैं, पुनरावर्ती प्रक्रिया का उपयोग करके इसमें तत्वों को पुन: व्यवस्थित करते हैं। हम वर्बोज़ कोड देखते हैं, संभावित रूप से टाइपोस के प्रति संवेदनशील होते हैं, लेकिन संभवतः स्मृति का उपयोग करते हुए, और जितनी जल्दी हो सके।

def sort_imp(arr: Array[Double]) {
  def swap(i: Int, j: Int) {
    val t = arr(i)
    arr(i) = arr(j)
    arr(j) = t
  }

  def sort1(l: Int, r: Int) {
    val pivot = arr((l + r) / 2)
    var i = l
    var j = r
    while (i <= j) {
      while (arr(i) < pivot) i += 1
      while (arr(j) > pivot) j -= 1
      if (i <= j) {
        swap(i, j)
        i += 1
        j -= 1
      }
    }
    if (l < j) sort1(l, j)
    if (i < r) sort1(i, r)
  }

  if (arr.length > 1)
    sort1(0, arr.length - 1)
}

— , , . , , (, GC).

def sort_fun(arr: Array[Double]): Array[Double] = {
  if (arr.length <= 1) 
    arr
  else {
    val pivot = arr(arr.length / 2)
    Array.concat(
      sort_fun(arr filter (pivot > _)),
      arr filter (pivot == _),
      sort_fun(arr filter (pivot < _))
    )
  }
}

($ sbt run) 10 . :

• — 2.5
• — 40

, java 3.6 .

UPD
LLVM nativeMode := «release» «immix gc», :

• — 2.3
• — 63

Rust:

— , , , , , . , borrow-checker.

fn sort_imp(arr: &mut Vec<f64>) {
  fn swap(arr: &mut Vec<f64>, i: usize, j: usize) {
    let t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
  };

  fn sort1(arr: &mut Vec<f64>, l: usize, r: usize) {
    let pivot = arr[(l + r) / 2];
    let mut i = l;
    let mut j = r;
    while i <= j {
      while arr[i] < pivot { i += 1; }
      while arr[j] > pivot { j -= 1; }
      if i <= j {
        swap(arr, i, j);
        i += 1;
        j -= 1;
      }
    }
    if l < j { sort1(arr, l, j); }
    if i < r { sort1(arr, i, r); }
  };

  if arr.len() > 1 {
    sort1(arr, 0, arr.len() - 1);
  }
}

— , , Rust , .

iter() filter() , x &&f64, **. . append() , , .

fn sort_fun(arr: Vec<f64>) -> Vec<f64> {
  if arr.len() <= 1 {
    arr
  } else {
    let pivot = arr[arr.len() / 2];
    let mut a = Vec::<f64>::with_capacity(arr.len());
    a.append(&mut sort_fun(arr.iter().filter(|x| pivot > **x).cloned().collect()));
    a.append(&mut arr.iter().filter(|x| pivot == **x).cloned().collect());
    a.append(&mut sort_fun(arr.iter().filter(|x| pivot < **x).cloned().collect()));
    a
  }
}

UPD
:

fn sort_fun(arr: Vec<f64>) -> Vec<f64> {
    if arr.len() <= 1 {
        arr
    } else {
        let pivot = arr[arr.len() / 2];
        [
            sort_fun(arr.iter().filter(|&&x| pivot > x).cloned().collect()),
            arr.iter().filter(|&&x| pivot == x).cloned().collect(),
            sort_fun(arr.iter().filter(|&&x| pivot < x).cloned().collect()),
        ]
        .concat()
    }
}

, — iter().filter(...).chain(...). zero-cost, , , — . , .

— , — , ( ).

($ cargo build --release):

• — 2
• — 9

— 650 .

:

, — , . , — , Rust -, , Rust , (, null ).

-, zero-cost — . Rust — - . , 2019 Scala Rust .

Scala.
Rust.

.