小编Kol*_*Kir的帖子

我试图理解外部合并排序算法是如何工作的(我看到了相同问题的一些答案,但没有找到我需要的东西).我正在阅读Jeffrey McConnell撰写的"分析算法"一书,我正在尝试实现那里描述的算法.

例如,我有输入数据:3,5,1,2,4,6,9,8,7,我只能将4个数字加载到内存中.

我的第一步是读取4个数字块的输入文件,在内存中对它们进行排序,然后将一个写入文件A,然后写入文件B.

我有:

A:[1,2,3,5][7]  
B:[4,6,8,9]

现在我的问题是,如果它们不适合内存,我如何将这些文件中的块合并到较大的文件中呢？杰弗里麦康奈尔写道,我需要阅读半块并将它们合并到下一个文件C和D.

但我得错了序列:

C:[1,2,4,6,3,8,5,9]
D:[7]

有人可以提供分步说明的例子吗？

PS:我理解如何通过读取文件来合并数字,但是如何使用内存缓冲区来减少I/O操作呢？

我编写了程序,并在Intel Core i5-2500上的Visual Studio 2010中为x64和x86平台编译.x64版本执行大约需要19秒,x86大约需要17秒.这种行为的原因是什么？

#include "timer.h"

#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>

/********************DECLARATIONS************************************************/
class Vector
{
public:
    Vector():x(0),y(0),z(0){}

    Vector(double x, double y, double z)
        : x(x)
        , y(y)
        , z(z)
    {
    }

    double x;
    double y;
    double z;
};


double Dot(const Vector& a, const Vector& b)
{
    return a.x * b.x + a.y * b.y + a.z * b.z;
}


class Vector2
{
public:
    typedef double value_type;

    Vector2():x(0),y(0){}

    Vector2(double x, double y)
        : x(x)
        , …

我正在学习Haskell并尝试编写代码以并行执行,但Haskell总是按顺序运行它.当我使用-N2运行时标志执行时,执行的时间比省略此标志要多.

这是代码:

import Control.Parallel
import Control.Parallel.Strategies

fib :: Int -> Int
fib 1 = 1
fib 0 = 1
fib n = fib (n - 1) + fib (n - 2)

fib2 :: Int -> Int
fib2 n = a `par` (b `pseq` (a+b))
    where a = fib n
          b = fib n + 1

fib3 :: Int -> Int
fib3 n = runEval $ do
                a <- rpar (fib n)
                b <- rpar (fib n + 1) …

我无法理解如何在具有下限（不是需求）的网络中找到循环流。我找到了下一个包含问题描述和解决策略的文档：

1. https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/flowext.pdf
2. http://homes.cs.washington.edu/~anderson/iucee/Slides_421_06/Lecture24_25_26.pdf
3. http://web.engr.illinois.edu/~jeffe/teaching/algorithms/2009/notes/18-maxflowext.pdf

让我们考虑一个具有以下边的网络（l - 下限，c - 容量）：

1 -> 2 : l = 1 c = 3

2 -> 3 : l = 2 c = 4

3 -> 1 : l = 1 c = 2

据我了解，要解决这个问题，我们应该采取以下步骤：

1. 把这个问题转化为“有需求的流通问题”。这可以通过下一个公式 dv' = dv - (Lin - Lout) 来完成，其中 'dv' 是原始顶点需求（在我们的例子中它等于 0），'Lin' - 顶点输入边下界的总和，以及 ' Lout' - 顶点输出边下界的总和。
2. 将边容量更新为 c' = c - l
3. 将带有边的源顶点 S 添加到 dv < 0 且容量为“-dv”的每个顶点
4. 添加接收器顶点 T 和每个顶点的边，dv > 0，容量为“dv”
5. 使用任何算法（例如 Edmonds-Karp 算法）在新网络中找到最大流量。
6. 如果最大流的值等于与 …

我正在尝试编写一个Haskell程序来解析大文本文件(大约14Gb),但我无法理解如何从内存中释放未使用的数据或不在foldr期间使堆栈溢出.这是程序源:

import qualified Data.ByteString.Lazy.Char8 as LBS
import qualified Data.ByteString.Lex.Lazy.Double as BD
import System.Environment


data Vertex = 
    Vertex{
     vertexX :: Double,
     vertexY :: Double,
     vertexZ :: Double}
    deriving (Eq, Show, Read)

data Extent = 
    Extent{
     extentMax :: Vertex,
     extentMin :: Vertex}
    deriving (Eq, Show, Read)

addToExtent :: Extent -> Vertex -> Extent
addToExtent ext vert = Extent vertMax vertMin where
                        (vertMin, vertMax) = (makeCmpVert max (extentMax ext) vert, makeCmpVert min (extentMin ext) vert) where
                            makeCmpVert f v1 v2 = Vertex(f (vertexX …

我在Haskell编写了一个程序,它必须加载并解析UTF8中的大文本文件.该文件表示每行上具有键:值对的字典.在我的程序中,我想要一个Data.Map容器​​来进行快速字典搜索.我的文件大约是40MB,但在加载到我的程序后,使用了1.5 GB的RAM,并且从未释放过.我做错了什么？是否预期使用内存？

这是我的程序中的代码示例:

模块主要在哪里

import Engine

import Codec.Archive.Zip
import Data.IORef
import System.IO
import System.Directory
import qualified System.IO.UTF8 as UTF8
import qualified Data.ByteString.Lazy as B
import qualified Data.ByteString.UTF8 as BsUtf
import qualified Data.Map as Map

import Graphics.UI.Gtk
import Graphics.UI.Gtk.Glade

maybeRead :: Read a => BsUtf.ByteString -> Maybe a
maybeRead s = case reads $ BsUtf.toString s of
     [(x, "")] -> Just x
     _         -> Nothing    

parseToEntries :: [BsUtf.ByteString] -> [(BsUtf.ByteString, Int)]
parseToEntries [] = []
parseToEntries (x:xs) = let (key, svalue) …