小编use*_*412的帖子

用错字匹配字符串的快速方法

我有很多字符串(城市名称),即使用户打错字,我也想找到城市的名称。

用户键入“ chcago”,系统将找到“ Chicago”

当然,我可以为列表中的所有字符串计算查询的Levenshtein距离,但这将非常慢。

有什么有效的方法可以执行这种字符串匹配吗?

string algorithm performance match fuzzy-comparison

5
推荐指数
1
解决办法
1747
查看次数

从wikimedia commons获取缩略图

我确实有来自wikimedia commons的文件名,我想直接访问缩略图.

示例: Tour_Eiffel_Wikimedia_Commons.jpg

我找到了一种方法来获取包含我想要的缩略图的网址的json数据:

https://en.wikipedia.org/w/api.php?action=query&titles=Image:Tour_Eiffel_Wikimedia_Commons.jpg&prop=imageinfo&iiprop=url&iiurlwidth=200
Run Code Online (Sandbox Code Playgroud)

但我不想要另一个请求.有没有办法直接访问缩略图?

thumbnails wikipedia-api

5
推荐指数
1
解决办法
869
查看次数

HashSet<int> 和 List<int> 的快速交集

我有一个HashSet<int>和一个List<int>(Hashset 大约有 300 万个项目,List 大约有 300k 个项目)。

我目前使用它们相交

var intersected = hashset.Intersect(list).ToArray();
Run Code Online (Sandbox Code Playgroud)

我想知道是否有更快的方法来做到这一点。也许并行?

c# algorithm performance intersection hashset

5
推荐指数
1
解决办法
1295
查看次数

Javascript:Concat布尔函数

我想写一个过滤多个标准数据的方法.这些标准应作为函数传递给filter-function,例如:

var products = [/* some data */];
function filterMyProducts(criteria) {
   return products.filter(/* I'm asking for this code */);
}

function cheap(product) {
    return product.price < 100;
}

function red(product) {
    return product.color == "red";
}

// find products that are cheap and red
var result = filterMyProducts([cheap, red]);
Run Code Online (Sandbox Code Playgroud)

如何将数组中传递的条件与过滤器函数结合起来?我希望它们与布尔AND结合使用.

javascript boolean concat filter

3
推荐指数
1
解决办法
676
查看次数

从二进制文件中读取巨型 int 数组

任务

我有一个包含整数的巨大文件(约 20 GB),想用 C# 读取它们。

简单的方法

将文件读取到内存(字节数组)非常快(使用 SSD,整个文件适合内存)。但是,当我使用二进制读取器(通过内存流)读取这些字节时,ReadInt32 方法比将文件读取到内存所需的时间要长得多。我预计磁盘 IO 是瓶颈,但事实是转换!

想法和问题

有没有一种方法可以直接将整个字节数组转换为 int 数组,而不必使用 ReadInt32 方法将其一一转换?

class Program
{
    static int size = 256 * 1024 * 1024;
    static string filename = @"E:\testfile";

    static void Main(string[] args)
    {
        Write(filename, size);
        int[] result = Read(filename, size);
        Console.WriteLine(result.Length);
    }

    static void Write(string filename, int size)
    {
        Stopwatch stopwatch = new Stopwatch();
        stopwatch.Start();
        BinaryWriter bw = new BinaryWriter(new FileStream(filename, FileMode.Create), Encoding.UTF8);
        for (int i = 0; i < size; i++)
        { …
Run Code Online (Sandbox Code Playgroud)

c# binary performance casting

3
推荐指数
1
解决办法
2834
查看次数

从多边形计算对偶图

任务

从一组不重叠(但接触)的多边形计算对偶图。

例子

多边形ABC,它们部分共享的坐标 1-22(黄色)和对偶图(蓝色)。

多边形及其对偶图

数据

我有一组S多边形。每个多边形P i都表示为坐标的有序列表。多边形P i的边ab表示为P i,(a,b)

主意

多边形代表对偶图的面和节点。为了识别多边形P i的相邻面,只需将P i的每条边与每个其他多边形P j的每条边进行比较。如果边由另一个多边形共享,则P iP j相邻。

这将创建大量的多条边,稍后可以将其删除。

问题

该算法效率不高,因为它的运行时间复杂度为O(E 2 ),其中E表示多边形集合S的边数。

改进思路

第一步创建边缘索引。这会将运行时间减少到O(2×E) = O(E)

删除度数为 2 的每个节点。(我认为这不会影响对偶图?)

问题

  • 我走在正确的轨道上吗?
  • 是否有任何经过批准的算法可以完成此任务?

algorithm geometry graph computational-geometry planar-graph

2
推荐指数
1
解决办法
1508
查看次数

更高效的结构为unordered_map <pair <int,int>,int>

我有大约20,000,000 pair<int, int>,我需要与ints联系.我这样做了unordered_map<pair<int, int>, int>.分析我的算法表明检查条目是否存在

bool exists = myMap[make_pair(a, b)] != NULL
Run Code Online (Sandbox Code Playgroud)

是性能瓶颈.我认为从a中检索这些信息unordered_map会非常快,因为它是O(1).但如果常数很大,则恒定时间可能会很慢......

我的哈希函数是

template <>
struct tr1::hash<pair<int, int> > {
public:
        size_t operator()(pair<int, int> x) const throw() {
             size_t h = x.first * 1 + x.second * 100000;
             return h;
        }
};
Run Code Online (Sandbox Code Playgroud)

你知道我的问题有更好的数据结构吗?

显然,我不能只将信息存储在矩阵中,因此内存量不适合现有的任何计算机.我所知道的所有分布都是myMap[make_pair(a, a)]不存在的a.并且所有ints都在从0到大约20,000,000的连续范围内.

可以把它想象成20,000,000x20,000,000的稀疏矩阵,大约有20,000,000个条目但从不在主对角线上.

建议

将一vector<pair<int, int>>*(阵列Ñ预期的条目)要快?查找a将是微不足道的(只是数组的索引),然后我将迭代向量,比较对的firstb.

大新闻

我上传了原始数据,因此您可以看到结构.

c++ algorithm performance unordered-map map

1
推荐指数
1
解决办法
2480
查看次数

Tarjan 算法的非递归版本

我有以下 Tarjan 算法的(递归)实现来查找图中的强连通分量,并且它工作正常:

public class StronglyConnectedComponents
{
    public static List<List<int>> Search(Graph graph)
    {
        StronglyConnectedComponents scc = new StronglyConnectedComponents();
        return scc.Tarjan(graph);
    }

    private int preCount;
    private int[] low;
    private bool[] visited;
    private Graph graph;
    private List<List<int>> stronglyConnectedComponents = new List<List<int>>();
    private Stack<int> stack = new Stack<int>();

    public List<List<int>> Tarjan(Graph graph)
    {
        this.graph = graph;
        low = new int[graph.VertexCount];
        visited = new bool[graph.VertexCount];

        for (int v = 0; v < graph.VertexCount; v++) if (!visited[v]) DFS(v);

        return stronglyConnectedComponents;
    }

    public void DFS(int v) …
Run Code Online (Sandbox Code Playgroud)

c# algorithm graph-algorithm tarjans-algorithm

1
推荐指数
1
解决办法
1885
查看次数