我正在研究一个项目,其重点是使用术语重写来解决/简化固定大小的位向量算术问题,这对于某些决策程序(例如基于钻头爆破的程序)的先前步骤是有用的.术语重写可以完全解决问题,或者产生更简单的等效问题,因此两者的组合可以导致相当大的加速.
我知道许多SMT求解器实现了这种策略(例如Boolector,Beaver,Alt-Ergo或Z3),但很难找到详细描述这些重写步骤的论文/技术报告/等.一般来说,我只发现了作者在几段中描述这种简化步骤的论文.我想找一些文件详细解释术语重写的用法:提供规则的例子,讨论AC重写和/或其他等式公理的便利性,重写策略的使用等.
目前,我刚刚找到了技术报告"固定宽度位向量的决策程序",描述了CVC Lite执行的规范化/简化步骤,我想找到更多这样的技术报告!我还发现了一张关于STP术语重写的海报,但这只是一个简短的总结.
我已经访问了那些SMT求解器的网站,我在他们的出版物页面中搜索过......
我将不胜感激任何参考,或任何有关如何在当前版本的知名SMT求解器中使用术语重写的解释.我对Z3特别感兴趣,因为它看起来有一个最聪明的简化阶段.例如,Z3 3.*引入了一个新的位向量决策程序,但遗憾的是,我无法找到任何描述它的论文.
一个演示问题:给定两个std::bitset<N>S,a并b检查是否有任何比特都设定a和b.
这个问题有两个相当明显的解决方案.这很糟糕,因为它会创建一个新的临时位集,并复制各种位置的值只是为了抛弃它们.
template <size_t N>
bool any_both_new_temp(const std::bitset<N>& a, const std::bitset<N>& b)
{
return (a & b).any();
}
这个解决方案很糟糕,因为它一次只有一点,这不太理想:
template <size_t N>
bool any_both_bit_by_bit(const std::bitset<N>& a, const std::bitset<N>& b)
{
for (size_t i = 0; i < N; ++i)
if (a[i] && b[i])
return true;
return false;
}
理想情况下,我将能够做这样的事情,在这里block_type是uint32_t或任何类型bitset的存储:
template <size_t N>
bool any_both_by_block(const std::bitset<N>& a, const std::bitset<N>& b)
{
typedef std::bitset<N>::block_type block_type;
for …我正在实现一个Bit Vector类作为练习,但是只知道Rust不到一周,我遇到了以下代码的问题:
use std::cmp::Eq;
use std::ops::BitAnd;
use std::ops::Index;
use std::ops::Not;
struct BitVector<S = usize>
where S: Sized + BitAnd<usize> + Not + Eq {
data: Vec<S>,
capacity: usize
}
impl<S> BitVector<S>
where S: Sized + BitAnd<usize> + Not + Eq {
fn with_capacity(capacity: usize) -> BitVector {
let len = (capacity / (std::mem::size_of::<S>() * 8)) + 1;
BitVector { data: vec![0; len], capacity: capacity }
}
}
impl<S> Index<usize> for BitVector<S>
where S: Sized + BitAnd<usize> + Not + Eq …在我正在进行的一项任务中,我们需要使用位向量,但我不确定如何在Python中执行此操作.它们应该能够从4位到20位.我以前从未使用过位向量,但我想可以创建一个使用通常的AND/OR/XOR操作操作的无符号字节数组.
这里的重要限制是:除了标准Python提供的库之外,我不能依赖任何库.
我想我知道如何使用8位无符号字节的数组在C中执行此操作:例如,将零数组的第18位转换为1,我会做类似my_bit_array [3]&= 1 << 2的操作
但由于Python是动态类型的,并且没有内置数组类型,我将如何以pythonic方式执行此操作？
是否有可能(如何？)表达大小为20的位向量？我在考虑制作一个24位/ 3字节向量并忽略4位.
我正在学习C/C++编程并遇到过"位数组"或"位向量"的用法.我无法理解他们的目的？这是我的疑惑 -
int数组吗？(当然更多的记忆,但..)我正在寻找应用程序,以便我能更好地理解.对于Eg -
问:您将获得一个包含范围内的整数(1到1百万)的文件.有一些重复,因此缺少一些数字.找到找到丢失数字的最快方法？
对于上面的问题,我已经阅读了告诉我使用位数组的解决方案.如何将每个整数存储一下？
最近我听说过位向量,但我真的找不到任何关于这个主题的有用信息或教程.能否请您推荐一本关于如何实现自己的位向量类的书或快速教程？谢谢.
--- ///我无法回答我自己的问题,所以我决定编辑这篇文章.这就是我刚刚发现的:"游戏程序员的数据结构 - Ron Penton和Andre Lamothe".第4章,Bitvectors.本书详细解释了位向量,以及如何自己创建位向量类.玩得开心.
是否有一些相当快的代码可以帮助我快速搜索大的位图(几兆字节)运行连续的零或一位？
通过"合理快速",我的意思是可以利用机器字大小并同时比较整个单词,而不是进行逐点分析,这是非常慢的(例如一个人vector<bool>).
它对于例如在卷的位图中搜索可用空间(用于碎片整理等)非常有用.
目前使用行程长度编码来编码位向量,当前运行时间是2log(i),其中是运行的大小.还有另一种方法可以将其归结为log(i)吗？谢谢.
这是Gayle Laakmann McDowell 撰写的Cracking the Coding Interview中的一个问题:
实现算法以确定字符串是否具有所有唯一字符.如果您不能使用其他数据结构怎么办？
作者写道:
我们可以通过使用位向量来减少空间使用量.我们假设,在下面的代码,该字符串只有较低的情况下
'a'通过'z'.这将允许我们只使用一个int.
作者有这个实现:
public static boolean isUniqueChars(String str) {
int checker = 0;
for (int i = 0; i < str.length(); ++i) {
int val = str.charAt(i) - 'a';
if ((checker & (1 << val)) > 0)
return false;
checker |= (1 << val);
}
return true;
}
让我们说我们摆脱了"字符串只是小写'a'通过'z'" 的假设.相反,该字符串可以包含任何类型的字符ASCII字符或Unicode字符.
有没有像作者那样有效的解决方案(或者一种与作者一样高效的解决方案)？
相关问题:
我们有一个包含许多实例的类,并遇到内存问题.因此,我们尝试减少这个类的内存需求.一个想法是以下.
该类有许多布尔实例变量,每个变量在初始实现中占用一个单词.可以想到将它们组合到存储在int中的迷你位向量,使得它们的组合存储器要求将是一个字.
但我怀疑Java VM正在进行这种优化,因此手动执行它不会获得任何额外的节省.对？