برای شخص بنده با خواندن کد پایتون خیلی راحت‌تر میتونم الگوریتم را بفهمم.اینجا به ترتیب کد راست و پایتون الگوریتم وارشال برای بدست آوردن بستار متعدی یک ماتریس باینری رابطه قرار داده شده. همچنین پیوند کد در گیت‌هاب گیست نیز زیر تکه کد را اضافه کرده‌ام. علاوه بر این‌ها زمان اجرا شدن این کد‌ها برای راست و پایتون در گیست مورد نظر به صورت کامنت نوشته شده است.توجه کنید که در هر دو زبان با حلقه 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
پیوند کد پایتون در گیت‌هاب گیست(به همراه زمان اجرا روی لپ‌تاپ بنده)
