selen 0.15.5

Constraint Satisfaction Problem (CSP) solver
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

/// Simple benchmark focused on small domains to demonstrate BitSet advantages
use std::time::Instant;
use selen::constraints::gac::{SparseSetGAC, Variable};
use selen::constraints::gac_bitset::BitSetGAC;

fn main() {
    println!("BitSet vs SparseSet Performance Test");
    println!("===================================");
    
    let iterations = 10000;
    let test_cases = vec![
        (20, 5),   // 20 variables, domain 1-5
        (50, 10),  // 50 variables, domain 1-10  
        (100, 20), // 100 variables, domain 1-20
    ];
    
    for (num_vars, domain_size) in test_cases {
        println!("\nTest: {} variables, domain 1-{}", num_vars, domain_size);
        
        // Benchmark SparseSet
        let mut sparseset_time = 0u128;
        for _ in 0..iterations {
            let mut gac = SparseSetGAC::new();
            let variables: Vec<Variable> = (0..num_vars).map(|i| Variable(i)).collect();
            
            let start = Instant::now();
            
            // Add variables and do basic operations
            for &var in &variables {
                gac.add_variable(var, 1, domain_size as i32);
            }
            
            // Remove some values and check domains
            for (i, &var) in variables.iter().enumerate().take(10) {
                gac.remove_value(var, ((i % domain_size) + 1) as i32);
                let _ = gac.get_domain_values(var);
            }
            
            sparseset_time += start.elapsed().as_nanos();
        }
        sparseset_time /= iterations as u128;
        
        // Benchmark BitSet
        let mut bitset_time = 0u128;
        for _ in 0..iterations {
            let mut gac = BitSetGAC::new();
            let variables: Vec<Variable> = (0..num_vars).map(|i| Variable(i)).collect();
            
            let start = Instant::now();
            
            // Add variables and do basic operations
            for &var in &variables {
                gac.add_variable(var, 1, domain_size as i32);
            }
            
            // Remove some values and check domains
            for (i, &var) in variables.iter().enumerate().take(10) {
                gac.remove_value(var, ((i % domain_size) + 1) as i32);
                let _ = gac.get_domain_values(var);
            }
            
            bitset_time += start.elapsed().as_nanos();
        }
        bitset_time /= iterations as u128;
        
        println!("SparseSet: {:>6} ns", sparseset_time);
        println!("BitSet:    {:>6} ns ({:.2}x speedup)", bitset_time, sparseset_time as f64 / bitset_time as f64);
        
        // Test alldiff propagation specifically
        println!("\nAllDiff propagation test:");
        
        // SparseSet alldiff
        let mut sparseset_alldiff_time = 0u128;
        for _ in 0..(iterations / 10) {
            let mut gac = SparseSetGAC::new();
            let variables: Vec<Variable> = (0..10).map(|i| Variable(i)).collect();
            
            for &var in &variables {
                gac.add_variable(var, 1, domain_size as i32);
            }
            
            let start = Instant::now();
            
            // Assign some variables and propagate manually
            for i in 0..5 {
                gac.assign_variable(variables[i], (i + 1) as i32);
                // Remove assigned values from other variables
                for j in (i + 1)..10 {
                    gac.remove_value(variables[j], (i + 1) as i32);
                }
            }
            
            sparseset_alldiff_time += start.elapsed().as_nanos();
        }
        sparseset_alldiff_time /= (iterations / 10) as u128;
        
        // BitSet alldiff with built-in propagation
        let mut bitset_alldiff_time = 0u128;
        for _ in 0..(iterations / 10) {
            let mut gac = BitSetGAC::new();
            let variables: Vec<Variable> = (0..10).map(|i| Variable(i)).collect();
            
            for &var in &variables {
                gac.add_variable(var, 1, domain_size as i32);
            }
            
            let start = Instant::now();
            
            // Use built-in alldiff propagation
            for i in 0..5 {
                gac.assign_variable(variables[i], (i + 1) as i32);
            }
            let _ = gac.propagate_alldiff(&variables);
            
            bitset_alldiff_time += start.elapsed().as_nanos();
        }
        bitset_alldiff_time /= (iterations / 10) as u128;
        
        println!("SparseSet AllDiff: {:>6} ns", sparseset_alldiff_time);
        println!("BitSet AllDiff:    {:>6} ns ({:.2}x speedup)", bitset_alldiff_time, sparseset_alldiff_time as f64 / bitset_alldiff_time as f64);
    }
    
    println!("\n=== Conclusion ===");
    println!("For small domains (≤64 values), BitSet operations provide:");
    println!("• Faster domain operations due to bit manipulation");
    println!("• More efficient alldiff propagation with Hall sets");
    println!("• Better cache locality with compact representation");
}