我有一个程序需要重复计算数据集的近似百分位数(顺序统计),以便在进一步处理之前删除异常值.我目前正在通过对值数组进行排序并选择适当的元素来实现这一目标; 这是可行的,但它在配置文件上是一个值得注意的昙花一现,尽管它是该计划的一个相当小的部分.

更多信息:

• 该数据集包含了100000浮点数字的顺序,并认为是"合理"分配 - 有不太可能在不久的特定值密度的重复,也不巨大的尖峰; 如果一些奇怪的原因分布为奇数,这是确定一个近似是不太准确的,因为数据很可能搞砸总之,进一步处理可疑.但是,数据不一定是统一的或正态分布的; 它不太可能退化.
• 近似解决方案没问题,但我确实需要了解近似值如何引入错误以确保其有效.
• 由于目标是去除异常值,我在任何时候都在同一数据上计算两个百分点:例如一个在95%,一个在5%.
• 该应用程序在C#中,在C++中有点繁重; 任何一个伪代码或预先存在的库都可以.
• 一个完全不同的去除异常值的方法也可以,只要它是合理的.
• 更新:似乎我正在寻找一种近似选择算法.

虽然这都是在一个循环中完成的,但每次数据(略微)都不同,因此重用数据结构并不像这个问题那样容易.

实施解决方案

使用Gronim建议的维基百科选择算法将这部分运行时间减少了大约20倍.

由于我找不到C#实现,这就是我想出的.即使对于小型输入,它也比Array.Sort更快; 在1000个元素上它快25倍.

public static double QuickSelect(double[] list, int k) {
    return QuickSelect(list, k, 0, list.Length);
}
public static double QuickSelect(double[] list, int k, int startI, int endI) {
    while (true) {
        // Assume startI <= k < endI
        int pivotI = (startI + endI) / 2; //arbitrary, but good if sorted
        int splitI = partition(list, startI, …

如何在F#中编写无操作语句？

具体来说,如何改进以下匹配语句的第二个子句:

match list with
    | [] -> printfn "Empty!"
    | _ -> ignore 0

我有一个带有多个应用程序Dispatcher(也就是GUI线程,也就是消息泵)的应用程序,以确保GUI的缓慢,无响应部分运行而不会过多地影响应用程序的其余部分.我也经常使用Task.

目前我已经有条件运行Actiona TaskScheduler或a的代码Dispatcher然后Task直接返回或通过手动创建一个使用TaskCompletionSource.然而,这种分裂的个性设计使得处理取消,异常等等都比我想要的复杂得多.我想在任何地方使用Tasks而且DispatcherOperation无处可去.要做到这一点,我需要在调度员上安排任务 - 但是如何？

如何获得TaskScheduler任何给定的Dispatcher？

编辑:在下面的讨论之后,我决定采用以下实现:

public static Task<TaskScheduler> GetScheduler(Dispatcher d) {
    var schedulerResult = new TaskCompletionSource<TaskScheduler>();
    d.BeginInvoke(() => 
        schedulerResult.SetResult(
            TaskScheduler.FromCurrentSynchronizationContext()));
    return schedulerResult.Task;
}

编辑2:为了实际演示为什么这仍然很重要,今天看看 stackoverflow自己的正则表达式导致的停机(2016-07-20)!

编辑:自从我第一次提出这个问题以来,这个问 请参阅下面的两个快速+兼容但不完全全功能的实现.如果你知道更多或更好的实现,请提及它们,这里仍然没有理想的实现!

哪里可以找到可靠的快速Regex实现？

有没有人知道正常的非回溯(System.Text.RegularExpressions回溯)线性时间正则表达式实现.NET或本机和从.NET合理使用？为了有用,它需要:

• 具有O(m*n)的正则表达式评估的最坏情况时间复杂度,其中m是正则表达式的长度,n是输入的长度.
• 具有正常的O(n)时间复杂度,因为几乎没有正则表达式实际触发指数状态空间,或者,如果它们可以,则仅在输入的微小子集上执行此操作.
• 具有合理的施工速度(即没有潜在的指数DFA)
• 旨在供人类使用,而不是数学家 - 例如我不想重新实现unicode字符类: .NET或PCRE样式字符类是一个加号.

奖励积分:

• 实用性的奖励点如果它实现了基于堆栈的功能,它允许它以消耗O(n + m)内存而不是O(m)内存为代价来处理嵌套.
• 奖励积分或者捕获子表达式或更换(如果有可能的子表达式匹配一个指数,然后枚举所有的人本质上是指数-但列举的前几个不应该是,同样的替代).您可以通过使用另一个来解决缺少任一功能的问题,因此使用其中一个功能就足够了.
• 将正则表达式作为第一类值处理的许多奖励点(因此你可以采用并集,交集,连接,否定 - 特别是否定和交集,因为通过正则表达式定义的字符串操作很难做到这一点)
• 懒惰匹配即在无限流上进行匹配而不将其全部放入内存中是一个优点.如果流不支持搜索,则捕获子表达式和/或替换不是(通常)单次传递.
• 反向引用已经消失,它们从根本上说是不可靠的; 即,在病理输入情况下,总是可以表现出指数行为.

存在这样的算法(这是基本的自动机理论......) - 但是有没有可从.NET访问的实际可用的实现？

背景:(你可以跳过这个)

我喜欢使用正则表达式进行快速和脏的文本清理,但我反复讨论perl/java/python/.NET使用的常见回溯NFA实现显示指数行为的问题.遗憾的是,一旦您开始自动生成正则表达式,这些情况就很容易触发.当您在匹配相同前缀的正则表达式之间切换时,即使非指数性能也会变得非常差 - 例如,在一个非常基本的示例中,如果您使用字典并将其转换为正则表达式,则期望可怕的性能.

为了快速了解为什么存在更好的实现并且从60年代开始,请参阅正则表达式匹配可以简单快速.

不太实用的选择:

• 几乎理想:FSA工具包.可以将正则表达式编译为DFA + NFA的快速C实现,允许换能器(!),具有第一类正则表达式(封装yay!),包括交叉和参数化的语法. 但它是在prolog ...(为什么有这种实用功能的东西在主流语言中不可用???)
• 快速但不切实际 …

我的代码充满了收藏 - 我想这不是一件不寻常的事情.但是,各种集合类型的使用并不明显,也不是微不足道的.通常,我想使用暴露"最佳"API的类型,并且语法噪音最小.(请参阅返回值数组时的最佳做法,使用列表数组 -可比较问题的最佳做法).有一些指南建议在API中使用哪些类型,但这些在普通(非API)代码中是不切实际的.

例如:

new ReadOnlyCollection<Tuple<string,int>>(
    new List<Tuple<string,int>> {
        Tuple.Create("abc",3),
        Tuple.Create("def",37)
    }
)

List这是一个非常常见的数据结构,但以这种方式创建它们会涉及相当多的语法噪音 - 而且它可能很容易变得更糟(例如字典).事实证明,许多列表永远不会改变,或者至少从未扩展.当然会ReadOnlyCollection引入更多的语法噪音,它甚至没有表达我的意思; 毕竟ReadOnlyCollection可以包装一个变异的集合.有时我在内部使用数组并返回一个IEnumerable表示意图.但是大多数这些方法都具有非常低的信噪比; 这对理解代码至关重要.

对于不是公共API 的99%的代码,没有必要遵循框架指南:但是,我仍然需要一个可理解的代码和一个传达意图的类型.

那么,处理使用小型集合传递价值的沼泽标准任务的最佳实践方法是什么？ 阵列应该List尽可能优先吗？还有别的吗？什么是最好的方式 - 清洁,可读,合理有效 - 传递这样的小集合？特别是,对于未阅读此问题并且不想阅读大量API文档但仍然了解其意图的未来维护者而言,代码应该是显而易见的.最大限度地减少代码混乱也是非常重要的- 所以这样的事情充其量是可疑的.具有小表面的主要API的罗嗦类型没有错,但不是大型代码库中的一般做法.ReadOnlyCollection

在没有大量代码混乱(例如显式类型参数)的情况下传递值列表的最佳方法是什么,但仍能清楚地传达意图？

编辑:澄清这是关于制作简短明了的代码,而不是关于公共API的.

受到Linq的污染,我不愿意放弃它.但是,对于某些事情,我只需要使用C++.

linq作为linq-consumer(即对我而言)的真正优势不在于表达树(操作起来很复杂),而是我可以轻松地混合和匹配各种功能.做的等价物.Where,.Select和.SelectMany, .Skip和.Take和.Concat存在C++ -风格的迭代器？

对于我编写的各种常用代码,这些都非常方便.

我不关心LINQ的细节,这里的关键问题是要能够在更高的层次来表达算法,而不是C++代码看起来像C#3.0.我希望能够表达"结果由每个序列的前n个元素串联形成",然后在需要新序列的地方重用这样的表达式 - 无需手动(并贪婪地)实例化中间体.

我试图调用一个.NET方法接受IEnumerable<T>来自F#的泛型,使用seq<U>U是T的子类.这不会像我预期的那样工作:

使用以下简单的打印机:

let printEm (os: seq<obj>) = 
    for o in os do
        o.ToString() |> printfn "%s"

这些是我得到的结果:

Seq.singleton "Hello World"  |> printEm // error FS0001; 
//Expected seq<string> -> 'a but given seq<string> -> unit

Seq.singleton "Hello World"  :> seq<obj> |> printEm // error FS0193;
//seq<string> incompatible with seq<obj>

Seq.singleton "Hello World"  :?> seq<obj> |> printEm // works!

Seq.singleton 42 :> seq<obj> |> printEm // error FS0193
Seq.singleton 42 :?> seq<obj> |> printEm // runtime InvalidCastException!
//Unable …

我想在没有Visual Studio设计者"帮助"的情况下创建和管理Windows服务应用程序.

由于这是.NET,并且由MSDN和设计人员做什么来判断,这意味着继承Installer,构建和处理ServiceProcessInstaller以及ServiceInstaller能够管理服务器的安装时执行.

运行时,这意味着创建一个ServiceBase子类并从Main使用ServiceBase.Run(并覆盖各种ServiceBase事件处理方法)开始.

但是,当我这样做时,Visual studio坚持将Installer和ServiceBase子类视为设计者编辑的文件.这并不完全有助于提高可读性,更不用说它通常根本无法处理手写代码. 我想避免设计师让事情变得易于管理(以避免模糊不清谁知道什么时候运行,特别是对于那些测试和调试很棘手的代码,例如必须安装才能运行的Windows服务),并且还能够在运行时指定服务名称,而不是在编译时指定服务名称 - 设计者不支持.

如何在没有所有垃圾的情况下创建Windows服务应用程序？

我一直在关注asp.net Web Api,我喜欢实现实用Web服务的简单性.

但是,我如何记录/指定这样实现的服务的接口？例如,我是否可以传递或生成没有.NET背景的Java人员,以便让他轻松调用和使用服务？我能给javascript的家伙什么？

理想情况下,我喜欢SOAP/XSD的好处或类似的东西(很容易用很好的类型对象反序列化),同时保留了一个可以从Web浏览器调用的服务(即支持非十分JSON).

更新

值得注意的是,自从我最初发布这个问题以来,我发现了更自然地处理这个问题的ServiceStack ; 支持JSON,SOAP和WSDL开箱即用,为客户选择相同的服务.如果你真的想要SOAP + JSON,它可能是一个比ASP.NET Web Api更好的框架.

当您在ASP.NET中收到上载文件时,通常通过HttpPostedFile对象执行此操作.收到的数据可通过HttpPostedFile.InputStream.然而这是在文档从来没有提到谁的属性,这将导致我相信我并不需要处理它自己是负责处置流,如果它是由ASP.NET框架,做当它这样做(比方说,如果我愿意,我可以在会话中保存流吗？).

现在,我没有收到那么多文件,我没有因为没有处理这个特定的流而遇到问题,但是为了清洁 - 有谁知道这里的设计合同是什么？