История изменений

Исправление zurg, 26.06.26 16:25 (текущая версия) :

ждём профи сишника,

Профи сишник, который действительно профи, воспользуется главным правилом - «если можешь избежать писания на сишке, не пиши на сишке» - особенно, такого рода прикладные вычислительные задачки. Ну в самом деле, питон есть, julia - если прямо вычислительные, всё это на 3 головы красивее, прямее и удобнее пыхосишек. Или вот на современной правильной сишке:

type Node = char;
type Graph = BTreeMap<Node, Vec<Node>>;

// в реальном коде будет fn graph_parser(txt: &str) -> Result<Graph, Err> с анализом ошибок парсенья
fn graph_parser(txt: &str) -> Graph {
   txt.lines().filter(|s| !s.is_empty()).map(|s| {
           let ss: Vec<&str> = s.split('→').collect();
           let nodes: Vec<_> = ss[1].split(',')
               .map(|s| s.trim().chars().next().unwrap()).collect();
           (ss[0].trim().chars().next().unwrap(), nodes)
       }).collect()
}
// самое простое, но может продавить стек
fn number_paths_rec(graph: &Graph, beg: Node, end: Node, mut num: u64) -> u64 {
   if graph[&beg].is_empty() { return num }
   for &node in graph[&beg].iter() {
       if node == end {
           num += 1;
       } else {
           num = number_paths_rec(graph, node, end, num);
       }
   }
   num
}
// это не продавит но расчёт графа в 3-4 раза медленнее
fn number_paths_tail(graph: &Graph, beg: Node, end: Node) -> u64 {
   fn iter(graph: &Graph, end: Node, mut stack: Vec<Node>, mut num: u64) -> u64 {
       match stack.pop() {
           None => num,
           Some(curr_node) => {
               for &node in graph[&curr_node].iter() {
                   if node == end {
                       num += 1;
                   } else {
                       stack.push(node);
                   }
               }
               iter(graph, end, stack, num)
           }
       }
   }
   iter(graph, end, vec![beg], 0)
}

fn main() {
   let graph_txt = "
   a → b, c, d, z
   b → d, e, f, z
   c → d, e, f, z
   d → e, f, z
   e → f, z
   f → g, h, j, z
   g → h, i, j, z
   h → i, j, k, z
   i → j, k, l, z
   j → k, m, z
   k → l, n, o, z
   l → m, z
   m → n, o, z
   n → o, z
   o → p, z
   p → q, z
   q → r, z
   r → s, z
   s → t, u, z
   t → u, v, z
   u → v, w, z
   v → w, z
   w → x, y, z
   x → y, z
   y → z";
   let graph = graph_parser(graph_txt);
   let t0 = Instant::now();
   // let val = number_paths_rec(&graph, 'a', 'z', 0);
   let val = number_paths_tail(&graph, 'a', 'z');
   let t0 = t0.elapsed().as_micros() as f64;
   println!("{} us, {}", t0, val);
}

общее время выполнения порядка 1-2 мс в зависимости от контейнеров и алгоритмов, на рекурисвных алгоритмах можно ещё и хэшмапы поперебирать

Исходная версия zurg, 26.06.26 16:22:

ждём профи сишника,

Профи сишник, который действительно профи, воспользуется главным правилом - «если можешь избежать писания на сишке, не пиши на сишке» - особенно такого рода прикладные вычислительные задачки. Ну в самом деле, питон есть, julia - если прямо вычислительные, всё это на 3 головы красивее, прямее и удобнее пыхосишек. Или вот на современной правильной сишке:

type Node = char;
type Graph = BTreeMap<Node, Vec<Node>>;

// в реальном коде будет fn graph_parser(txt: &str) -> Result<Graph, Err> с анализом ошибок парсенья
fn graph_parser(txt: &str) -> Graph {
   txt.lines().filter(|s| !s.is_empty()).map(|s| {
           let ss: Vec<&str> = s.split('→').collect();
           let nodes: Vec<_> = ss[1].split(',')
               .map(|s| s.trim().chars().next().unwrap()).collect();
           (ss[0].trim().chars().next().unwrap(), nodes)
       }).collect()
}
// самое простое, но может продавить стек
fn number_paths_rec(graph: &Graph, beg: Node, end: Node, mut num: u64) -> u64 {
   if graph[&beg].is_empty() { return num }
   for &node in graph[&beg].iter() {
       if node == end {
           num += 1;
       } else {
           num = number_paths_rec(graph, node, end, num);
       }
   }
   num
}
// это не продавит но расчёт графа в 3-4 раза медленнее
fn number_paths_tail(graph: &Graph, beg: Node, end: Node) -> u64 {
   fn iter(graph: &Graph, end: Node, mut stack: Vec<Node>, mut num: u64) -> u64 {
       match stack.pop() {
           None => num,
           Some(curr_node) => {
               for &node in graph[&curr_node].iter() {
                   if node == end {
                       num += 1;
                   } else {
                       stack.push(node);
                   }
               }
               iter(graph, end, stack, num)
           }
       }
   }
   iter(graph, end, vec![beg], 0)
}

fn main() {
   let graph_txt = "
   a → b, c, d, z
   b → d, e, f, z
   c → d, e, f, z
   d → e, f, z
   e → f, z
   f → g, h, j, z
   g → h, i, j, z
   h → i, j, k, z
   i → j, k, l, z
   j → k, m, z
   k → l, n, o, z
   l → m, z
   m → n, o, z
   n → o, z
   o → p, z
   p → q, z
   q → r, z
   r → s, z
   s → t, u, z
   t → u, v, z
   u → v, w, z
   v → w, z
   w → x, y, z
   x → y, z
   y → z";
   let graph = graph_parser(graph_txt);
   let t0 = Instant::now();
   // let val = number_paths_rec(&graph, 'a', 'z', 0);
   let val = number_paths_tail(&graph, 'a', 'z');
   let t0 = t0.elapsed().as_micros() as f64;
   println!("{} us, {}", t0, val);
}