برای شخص بنده با خوندن کد پایتون خیلی راحت‌تر میتونم الگوریتم را بفهمم.اینجا به ترتیب کد راست و پایتون الگوریتم وارشال برای بدست آوردن بستار متعدی یک ماتریس باینری رابطه به همراه لینک کد در گیت‌هاب گیست قرار داده شده.ضمن اینکه زمان اجرا شدن این کد‌ها برای راست و پایتون در گیست مورد نظر به صورت کامنت قرار داده شده است.توجه کنید که در هر دو زبان با حلقه for این پیاده‌سازی انجام شده و در صورتی که با استفاده از map همین الگوریتم را پیاده کنید پرفرمنس احتمالا بهبود خواهد یافت.
هشدار! کد راست با اینکه به درستی کار می‌کند اما ممکن است به روش خود راست نوشته نشده باشد و در آن عادت‌های خوب برنامه‌نویسی رعایت نشده باشد!
// Code by Rust beginner, Farooq Karimi Zadeh
// Under CC0 1.0
// Warning! Code might not be idiomatic
fn main() {
let mut bin_matrix = [
[0, 1, 0, 0],
[1, 0, 1, 0],
[0, 0, 0, 1],
[0, 0, 0, 0]
];
const N:u32 = 300_000;
for _dummy in 0..N {
for k in 0..bin_matrix.len() {
let the_clone = bin_matrix;
for (i, row) in bin_matrix.iter_mut().enumerate() {
for (j, value) in row.iter_mut().enumerate() {
if *value == 0 {
*value = the_clone[i][k] & the_clone[k][j];
}
}
}
}
}
println!("{:?}", bin_matrix);
}
لینک کد راست در گیست
"""
Warshall algorithm
This calculates transitive closure for a given binary matrix
Author: Farooq Karimi Zadeh
Code is under CC0 1.0
"""
from pprint import pprint
def pretty_print_matrix(matrix):
pprint(matrix, width=len(matrix[0]) * 3 + 2)
n = int(3e5) # calculate n times
bin_matrix = [[0, 1, 0, 0], [1, 0, 1, 0], [0, 0, 0, 1], [0, 0, 0, 0]]
for dummy in range(n):
for k, _ in enumerate(bin_matrix):
for i, row in enumerate(bin_matrix):
for j, value in enumerate(row):
if not value:
bin_matrix[i][j] = bin_matrix[i][k] and bin_matrix[k][j]
if n == 1:
pretty_print_matrix(bin_matrix)
else:
pass # then we are benchmarking
