Last active
September 15, 2025 22:10
-
-
Save jweinst1/63c4eea5fb489e9508fea1c7e6644d10 to your computer and use it in GitHub Desktop.
Bit set in rust that stores vectors for membership
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| fn sub_distance<const S: usize>(v1:&[u64;S], v2:&[u64;S]) -> u64 { | |
| let mut total = 0; | |
| for i in 0..S { | |
| total += v1[i] - v2[i]; | |
| } | |
| return total; | |
| } | |
| fn and_pop_distance<const S: usize>(v1:&[u64;S], v2:&[u64;S]) -> u64 { | |
| let mut total = 0; | |
| for i in 0..S { | |
| total += (v1[i] & v2[i]).count_ones(); | |
| } | |
| return total as u64; | |
| } | |
| fn and_pop_shift_right_distance<const S: usize, const D:usize>(v1:&[u64;S], v2:&[u64;S]) -> u64 { | |
| const { | |
| assert!(D < 6); | |
| } | |
| let mut total = 0; | |
| for i in 0..S { | |
| total += (v1[i] & (v2[i] >> D)).count_ones(); | |
| } | |
| return total as u64; | |
| } | |
| fn check_memb<const S: usize, const B:usize>(key:&[u64;S], set:&[[u64;S];B]) -> bool { | |
| let part = &set[(key[0] as usize) & (B - 1)]; | |
| for i in 0..S { | |
| if key[i] & part[i] != key[i] { | |
| return false | |
| } | |
| } | |
| true | |
| } | |
| fn store_memb<const S: usize, const B:usize>(key:&[u64;S], set:&mut [[u64;S];B]) { | |
| const { | |
| assert!(B == 256); | |
| } | |
| let part = &mut set[(key[0] as usize) & (B - 1)]; | |
| for i in 0..S { | |
| part[i] |= key[i]; | |
| } | |
| } | |
| fn test1() { | |
| let mut k = [0b1101, 0b1001, 0b11111]; | |
| let mut s: [[u64; 3]; 256] = [[0; 3]; 256]; | |
| store_memb(&k, &mut s); | |
| println!("{:?}", check_memb(&k, &s)); | |
| k[2] = k[2] << 1; | |
| println!("{:?}", check_memb(&k, &s)); | |
| } | |
| fn main() { | |
| test1(); | |
| let mut s: [[u64; 3]; 256] = [[0; 3]; 256]; | |
| let mut k = [0, 0, 0]; | |
| let mut fakes = 0; | |
| for i in 0..10000 { | |
| if i % 2 == 0 { | |
| k[0] = i; | |
| k[2] = i + 95; | |
| store_memb(&k, &mut s); | |
| } | |
| } | |
| k[0] = 0; | |
| k[1] = 0; | |
| k[2] = 0; | |
| for i in 0..10000 { | |
| if i % 2 != 0 { | |
| k[0] = i; | |
| k[2] = i + 95; | |
| if check_memb(&k, &s) { | |
| fakes += 1; | |
| } | |
| } | |
| } | |
| println!("Fake count {:?}", fakes); | |
| println!("sub dist {:?}", sub_distance(&s[0], &s[1])); | |
| println!("shift and dist {:?}", and_pop_shift_right_distance::<3, 1>(&s[0], &s[1])); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment