小编Pet*_*iak的帖子

我理解为什么不能这样做的原因(重新平衡和东西):

iterator i = m.find(33);

if (i != m.end())
  i->first = 22;

但到目前为止,改变密钥的唯一方法(我知道)是从树中删除节点,然后使用不同的密钥插入值:

iterator i = m.find(33);

if (i != m.end())
{
  value = i->second;
  m.erase(i);
  m[22] = value;
}

由于更多原因,这似乎对我来说效率很低:

1. 遍历树三次(+余额)而不是两次(+余额)
2. 还有一个不必要的价值副本
3. 不必要的重新分配,然后重新分配树内的节点

我发现分配和释放是这三者中最差的.我错过了什么或有更有效的方法吗？

更新:我认为,从理论上讲,它应该是可能的,所以我不认为改变不同的数据结构是合理的.这是我想到的伪算法:

1. 找到树中我想要更改其键的节点.
2. 如果从树上分离(不要解除分配)
3. 重新平衡
4. 更改分离节点内的密钥
5. 将节点插回树中
6. 重新平衡

当人们想要遍历树并保持当前位置时,Zipper数据结构很棒,但是如果他们想要跟踪多个位置,应该使用哪种数据结构？

让我用例子解释一下:

• #haskell频道上的某个人告诉我,在yi编辑器中使用拉链来表示光标位置.这很棒,但是如果你想要两个游标怎么办呢.就像你想要表示选择一样,你需要知道选择的开始和结束.
• 在wikibooks的Minotaur示例中,他们使用Zipper来表示Minotaur在迷宫内的位置.如果我想将敌人添加到迷宫中,用拉链代表他们的位置就会有意义.
• 最后一个实际上来自我的迷你项目,它开始了:作为学习Haskell的一部分,我正在尝试使用cairo和gth2hs可视化树结构.到目前为止,这已经很顺利,但现在我想选择一个或多个节点,并能够移动它们.因为可以有多个选定节点,所以我不能只使用教科书中定义的Zipper.

有一个简单的(幼稚？)解决方案,类似于他们在XMonad的早期版本中使用的涉及作为解释的有限的地图在这里.

也就是说,例如,在我的示例项目的情况下,我将所选节点存储在索引映射中,并用索引替换它们在主结构中的表示.但是这种解决方案有很多缺点.就像上面链接中解释的那样,或者说,在我的例子的情况下,取消选择所有节点将需要搜索整个树.

在使用clang的线程消毒剂时,我们注意到了数据竞争警告.我们认为这是由于std :: string的copy-on-write技术不是线程安全的,但我们可能是错的.我们减少了对此代码的警告:

void test3() {
  std::unique_ptr<std::thread> thread;

  {
    auto output = make_shared<string>();
    std::string str = "test";
    thread.reset(new std::thread([str, output]() { *output += str; }));
    // The str string now goes out of scope but due to COW
    // the captured string may not have the copy of the content yet.
  }

  thread->join();
}

在使用线程清理程序编译时:

clang++ -stdlib=libc++ -std=c++11 -O0 -g -fsanitize=thread -lpthread -o test main.cpp

要么

clang++ -std=c++11 -O0 -g -fsanitize=thread -lpthread -o test main.cpp

并且当多次运行时,它最终会产生此警告:

WARNING: ThreadSanitizer: data race …

我正在尝试将Data.Binary.Put monad包装到另一个monad中,以便稍后我可以问一些问题,例如"它要写多少字节"或"文件中的当前位置是什么".但即使非常微不足道的包装如下:

data Writer1M a = Writer1M { write :: P.PutM a }
or
data Writer2M a = Writer2M { write :: (a, P.Put) }

创建一个巨大的空间泄漏,程序通常崩溃(占用4GB的RAM后).这是我到目前为止所尝试的:

-- This works well and consumes almost no memory.

type Writer = P.Put

writer :: P.Put -> Writer
writer put = put

writeToFile :: String -> Writer -> IO ()
writeToFile path writer = BL.writeFile path (P.runPut writer)

-- This one will cause memory leak.

data Writer1M a = Writer1M { write :: P.PutM …

我正试图找到一种正式的方式来考虑haskell中的空间复杂性.我发现这篇关于图形缩减(GR)技术的文章在我看来是一种方法.但是我在某些情况下应用它时遇到了问题.请考虑以下示例:

假设我们有一个二叉树:

data Tree = Node [Tree] | Leaf [Int]

makeTree :: Int -> Tree
makeTree 0 = Leaf [0..99]
makeTree n = Node [ makeTree (n - 1)
                  , makeTree (n - 1) ]

和两个遍历树的函数,一个(count1)流畅地流动,另一个(count2)一次在内存中创建整个树; 根据剖析器.

count1 :: Tree -> Int
count1 (Node xs) = 1 + sum (map count1 xs)
count1 (Leaf xs) = length xs

-- The r parameter should point to the …

我正在寻找一种算法,其中可以将连接节点组合并在一起以形成新组(通过在不同组的节点之间创建链接).并且可以对组进行分区以形成新分区.

与会员协议的共识风格(例如,在Raft论文中描述的那种)不同,在分区之后只有一个组可以保留,我希望每个新分区形成一个新组.

此外,我希望每个分区都有,每个成员都会同意哪个属于该分区,具有强大的一致性保证.

或者换句话说,我希望保留以下属性:在一个组进行成员资格更改后,如果属于原始组的两个节点仍然可以通信(两者之间有路径),则他们应该就序列达成一致发生在集团的变化.

我的理解是,每个新分区在某种意义上对不同的成员集合达成一致的事实意味着CAP定理的一致性部分是放松的.希望这样的协议可能存在(？).

我最近通过浏览网络了解UDP套接字,所有解释它的网页都提到UDP套接字是"少连接".如果我理解正确,这意味着一个人在两个套接字之间没有"连接",而是将数据报包发送到指定的端点,而不知道另一端是否在监听.

然后我开始阅读boost :: asio :: ip :: udp :: socket 文档,发现它提到了API:

• async_connect:启动异步连接.
• async_receive:在连接的套接字上启动异步接收.
• async_send:在连接的套接字上启动异步发送.

现在这对新手来说有点混乱.我可以找到3个可能的原因导致我的困惑(按照相似的顺序:))

1. 我错过了什么
2. asio实现在幕后做一些事情来虚拟化连接.
3. 文档错了

当你打开basic_datagram_socket :: async_connect的页面时,文档中也有一个小故障,例子中有实例化的TCP套接字(而不是UDP套接字).

有人请赐教吗？

我们正在使用NativeActivity类在Android上开发OpenGL游戏.到目前为止一切顺利,但现在我们需要访问一些似乎只能从Java获得的功能.

还有更多,但我们认为第一个有用的是访问显示器DPI.如上所述这里的Java代码如下所示:

DisplayMetrics metrics = new DisplayMetrics();
getWindowManager().getDefaultDisplay().getMetrics(metrics);

这是不幸的相应C++代码:

// My checking routine.
#define JNI_ASSERT(jni, cond) { \
  if (!(cond)) {\
    std::stringstream ss; \
    ss << __FILE__ << ":" << __LINE__; \
    throw std::runtime_error(ss.str()); \
  } \
  if (jni->ExceptionCheck()) { \
    std::stringstream ss; \
    ss << __FILE__ << ":" << __LINE__; \
    throw std::runtime_error("Exception: " + ss.str()); \
  } \
}

void print_dpi(android_app* app) {
  JNIEnv* jni;
  app->activity->vm->AttachCurrentThread(&jni, NULL);

  jclass activityClass = jni->FindClass("android/app/NativeActivity");
  JNI_ASSERT(jni, activityClass);

  jmethodID …

正如在我之前的问题中,我正在尝试将Data.Binary.Put monad包装到另一个monad中,以便稍后我可以问它"它要写多少字节"或"文件中的当前位置是什么"等问题.

之前,我认为理解为什么它在使用一个简单的(IdentityT？)包装器时会泄漏内存会导致我解决我的问题.但即使你们帮我解决了这个简单的包装器的问题,用StateT或WriterT之类的东西包装它仍然会消耗太多的内存(并且通常会崩溃).

例如,这是我试图包装它的一种方式,它为大输入泄漏内存:

type Out = StateT Integer P.PutM ()

writeToFile :: String -> Out -> IO ()
writeToFile path out = BL.writeFile path $ P.runPut $ do runStateT out 0
                                                         return ()

这是一个更完整的代码示例,演示了该问题.

我想知道的是:

1. 程序内部发生什么导致内存泄漏？
2. 我该怎么办才能修复它？

对于我的第二个问题,我想我应该更详细地解释一下我打算在磁盘上查看数据:它基本上是一个树结构,其中树的每个节点都表示为它的子节点的偏移表(加上一些附加数据).因此,要计算第n个孩子到偏移表中的偏移量,我需要知道子项0到n-1的大小加上当前偏移量(为了简化事情,假设每个节点都有固定数量的子节点).

谢谢你的期待.

更新:感谢nominolo我现在可以创建一个包裹Data.Binary.Put的monad,跟踪当前偏移并几乎不使用任何内存.这是通过放弃使用StateT转换器来支持使用Continuations的不同状态线程机制来完成的.

像这样:

type Offset = Int

newtype MyPut a = MyPut
  { unS :: forall r . (Offset -> a -> P.PutM r) -> Offset -> P.PutM r }

instance Monad MyPut where
  return a = MyPut …

我在一个单独的线程中的循环中运行acceptTCP侦听器的功能.我想优雅地关闭这个线程,但我看不到任何shutdown可以用来打破接受的机制.

我目前的方法看起来像这样:

use std::net::TcpListener;
use std::thread::spawn;

fn main() {
    let tcp_listener = TcpListener::bind((("0.0.0.0"), 0)).unwrap();
    let tcp_listener2 = tcp_listener.try_clone().unwrap();

    let t = spawn(move || {
        loop {
            match tcp_listener2.accept() {
                Ok(_) => { }
                Err(_) => { break; }
           }
        }
    });

    drop(tcp_listener);
    assert!(t.join().is_ok());
}

但这并不能解决问题(可能是因为我只删除了克隆的副本？).有关如何正确关闭此类线程的任何想法？

(作为参考,我在Rust用户论坛上也问过这个问题)