标签: sorted

对于那些你不熟悉的插值搜索,这是方法来搜索排序的数组,它是有可能快于二进制搜索的值.你看,第一和最后一个元素和(假设数组的内容是均匀分布的)线性插入到预测的位置.

例如:我们有长度100与阵列[0] = 0和阵列[99] = 99的阵列.如果我们正在寻找80中,它是直观的尝试阵列[80]在阵列[50],并且如果阵列是接近均匀分布的,所期望的运行时被减小到log(log(N))

对于数字,要检查的位置由等式定义: low + ((toFind - sortedArray[low]) * (high - low + 1)) / (sortedArray[high] - sortedArray[low]).

用于展示插值搜索的直观性质的常见示例是:想象试图在字典中找到"黄色"这个词.你不会使用二进制搜索并转到中途点.相反,你会去预期的位置.

人类可以自然地线性插值字符串,但我无法弄清楚它是如何编码的.我们如何线性插值字符串？

在Delphi 6中,如果您尝试将对象插入到已排序的TStringList(Sorted = true),则会抛出异常,警告您在排序列表上不允许使用InsertObject().如果调用InsertObject()必然意味着破坏列表的Sorted顺序,我可以理解这一点.但鉴于TStringList.Find()方法:

function TStringList.Find(const S: string; var Index: Integer): Boolean;

返回一个索引,告诉你如果给定字符串添加到列表中的插入索引应该是什么,使用该索引调用InsertObject()应该在操作后保持排序列表仍然按排序顺序.我已经检查了TStringList的Delphi源代码,它似乎证实了我的断言.

现在我只是为TStringList创建一个新的子类,它覆盖了InsertObject(),并且如果在排序列表中调用了InsertObject(),则不会抛出异常,但我想确保没有一些隐藏的危险我我只是没有看到.

- roschler

我想知道是否有人可以提供一些关于如何使分类集生成更有效的建议？

我正在开发一个项目,其中排名数据按小时计算并存储在数据库中.数据可以按成员性别,国家等进行过滤.大约有200万行需要处理,需要很长时间.

我们希望采用更实时的方法,在Redis中进行数据存储/排序/过滤以及每日清理重建.

在我的原型中,我正在为每个可能的过滤器组合创建一个有序集合,例如:leaderboard.au.male,leaderboard.au.female等.我编写了这个过程但是一旦你处理完每个案例就意味着有118个排序集创建.

理想情况下,我希望为每个包含其名称,性别和国家/地区的成员设置一个排名排序集和哈希集.然后使用Redis仅根据用户定义的过滤器返回已排序的设置值.(例如,只获得澳大利亚男性的排名).

这可以在Redis中原生吗？

我想得到一些反馈和建议,我正在考虑使用Redis排序集实现可搜索索引的两种方法.

情况和目标

我们目前有一些我们存储在Cassandra中的键值表,我们希望它们有索引.例如,一个表将包含人员的记录,Cassandra表将id作为其主键,序列化对象作为值.该对象将具有诸如first_name,last_name,last_updated等字段.

我们想要的是能够进行搜索,例如"last_name ='Smith'AND first_name>'Joel'","last_name <'Aaronson'","last_name ='Smith'AND first_name ='Winston'"等等.搜索应该产生匹配的ID,以便我们可以从Cassandra中检索对象.我认为上述搜索可以使用单个索引完成,按字典顺序排序为last_name,first_name和last_updated.如果我们需要使用不同顺序的某些搜索(例如"first_name ='Zeus'"),我们可以使用类似的索引来允许那些(例如first_name,last_updated).

我们正在考虑使用Redis,因为我们需要能够每分钟处理大量的写入操作.我已经阅读了Redis排序集的一些常用方法,并提出了两种可能的实现:

选项1:每个索引的单个排序集

对于last_name,first_name,last_updated的索引,我们在Redis下的密钥索引下有一个有序集:people:last_name:first_name:last_updated,其中包含格式为last_name的字符串:first_name:last_updated:id.例如:

史密斯:乔尔:1372761839.444:0azbjZRHTQ6U8enBw6BJBw

(对于分隔符,我可能会使用'::'而不是':'或其他东西来更好地处理字典顺序,但是现在让我们忽略它)

这些项目都将被赋予得分0,以便排序的集合将按字典顺序按字符串本身排序.如果我想做一个像"last_name ='smith'AND first_name <'bob'"这样的查询,我需要获取列表中'smith:bob'之前的所有项目.

据我所知,这种方法有以下缺点:

1. 没有Redis功能可根据字符串值选择范围.这个名为ZRANGEBYLEX的功能由Salvatore Sanfilippo在https://github.com/antirez/redis/issues/324上提出,但未实现,因此我必须使用二进制搜索找到端点并自行获取范围(可能使用Lua,或者在Python的应用程序级别,这是我们用来访问Redis的语言).
2. 如果我们想要为索引条目包含生存时间,那么最简单的方法是使用定期计划的任务遍历整个索引并删除过期的项目.

选项2:小型排序集,按last_updated排序

这种方法是类似的,除了我们会有许多较小的有序集合,每个集合都有一个类似时间的值,例如分数的last_updated.例如,对于相同的last_name,first_name,last_updated索引,我们将为每个last_name,first_name组合设置一个有序集.例如,密钥可能是索引:people:last_name = smith:first_name = joel,它将为我们称为Joel Smith的每个人创建一个条目.每个条目的id都是id,其得分是last_updated值.例如:

值:0azbjZRHTQ6U8enBw6BJBw; 得分:1372761839.444

这方面的主要优点是(a)搜索我们知道除了last_updated之外的所有字段都非常容易,并且(b)使用ZREMRANGEBYSCORE实现生存时间非常简单.

对我来说似乎非常大的缺点是:

1. 管理和搜索这种方式似乎更加复杂.例如,我们需要索引来跟踪其所有键(例如,我们希望在某些时候清理)​​并以分层方式执行此操作.诸如"last_name <'smith'"之类的搜索需要首先查看所有姓氏的列表以查找史密斯之前的那些,然后查找每个查找它包含的所有名字的人,然后查找每个姓氏.从排序集中获取所有项目.换句话说,很多组件需要建立和担心.

包起来

所以在我看来,尽管有其缺点,但第一种选择会更好.我非常感谢有关这两个或其他可能的解决方案的任何反馈(即使他们是我们应该使用除Redis之外的其他东西).

我想做一个有序的datagridview输入.以下代码片段并没有完全消除它; 即使我放了一个grd.Refresh,datagridview也不会显示更新的值.如果我按下向下箭头键并再次上升,网格就会刷新.有没有其他方法可以强制刷新datagridview的内容？

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;

namespace TestSortedInput
{
    public partial class Form1 : Form
    {
        DataTable _dt = new DataTable();

        public Form1()
        {
            InitializeComponent();

            grd.AllowUserToAddRows = false;

            _dt.Columns.Add("sort", typeof(int));
            _dt.Columns.Add("product", typeof(string));

            _dt.DefaultView.Sort = "sort";

            grd.DataSource = _dt;
        }

        private void dataGridView1_KeyUp(object sender, KeyEventArgs e)
        {
            if (e.KeyCode == Keys.Insert)
            {                
                if (e.Modifiers == 0)
                {
                    var r = _dt.NewRow();
                    r["sort"] = _dt.DefaultView.Count + 1;
                    r["product"] = "";

                    _dt.Rows.Add(r);
                } …

以防万一你错过了，问题是关于删除sorted数组上的重复项。可以应用非常快速的算法（与未排序的数组相比）来删除重复项。

• 如果您已经知道如何删除 SORTED 数组上的重复项，则可以跳过此步骤

例子：

var out=[];
for(var i=0,len=arr.length-1;i<len;i++){
    if(arr[i]!==arr[i+1]){
        out.push(arr[i]);
    }
}
out.push(arr[i]);

看到了吗，速度很快。我会尽力解释刚刚发生的事情。

排序后的数组 * 可能如下所示：

arr=[0,1,1,2,2,3,4,5,5,6,7,7,8,9,9,9];

*排序可以是 ASC 或 DESC，或者通过其他奇怪的方法，但重要的是每个重复的项目都是相邻的。

我们停下来是array.length-1因为我们没有任何东西可以检查

然后我们不管任何事情都添加了最后一个元素，因为：

案例一：

... ,9,9,9];//we have dup(s) on the left of the last element

案例B：

... ,7,9,10];//we don't have dup(s) on the left of the last element

如果您真的了解发生了什么，您就会知道我们没有9在案例 A 上添加任何内容。因此，无论我们是在案例 A 还是 B 上，我们都希望添加最后一个元素。

题：

这解释了，我想做同样的事情，但忽略以下undefined情况的价值：

var arr=[];arr[99]=1;//0 through 98 are undefined, but do NOT hold the undefined value …

使用Java，我有一个称为TestClass的类，该类具有一个名为Name的成员，该成员是一个字符串。我也有这种类型的ArrayList，它已经按名称按字母顺序排序。我想做的是找到放置TestClass新实例的最佳索引。到目前为止，我能想到的最好方法是：

public static int findBestIndex(char entry, ArrayList<TestClass> list){
    int desiredIndex = -1;
    int oldPivot = list.size();
    int pivot = list.size()/2;
    do
    {
        char test = list.get(pivot).Name.charAt(0);
        if (test == entry)
        {
            desiredIndex = pivot;
        }
        else if (Math.abs(oldPivot - pivot) <= 1)
        {
            if (test < entry)
            {
                desiredIndex = pivot + 1;
            }
            else
            {
                desiredIndex = pivot - 1;
            }
        }
        else if (test < entry)
        {
            int tempPiv = pivot;
            pivot = oldPivot - (oldPivot - pivot)/2; …

我有两个排序列表,都是非递减顺序.例如,我有一个带有元素的已排序链表[2,3,4,5,6,7...],另一个带有元素[5,6,7,8,9...].

我需要找到两个列表中的所有常见元素.我知道我可以使用for循环和嵌套循环来迭代所有匹配以找到相同的两个元素.但是,有没有另一种方法可以做到这一点,运行时间少于O(n^2)？

农产品协议

我一直试图在我的循环链表中调试一个问题12小时.该函数接收一个具有开始和光标字段的ADT.最初的虚拟单元指向自身.插入元素.不允许重复元素.

    int setInsertElementSorted(setADT buffer, setElementT E)
    {
        bool isUnique = true;
        cellT *previous;

        previous = buffer->start;
        buffer->cursor = buffer->start->next;

        while(buffer->cursor != buffer->start){
            if(buffer->cursor->value == E){
                isUnique = false;
            } else if(E < buffer->cursor->value)
                break;
              else {   
                previous = buffer->cursor;
                buffer->cursor = buffer->cursor->next;
            }
        }

        if(isUnique != false){
            cellT *newNode = malloc(sizeof(cellT));
            newNode->value = E;
            previous->next = newNode;
            newNode->next = buffer->cursor;

            buffer->count++;
            return (buffer->count);   
            }
    }

代码接受一系列整数,然后将它们排序到LL参数中.假设用于一组(因此没有重复输入).

输出为:9,8,7,6,5,4,3,2,1

是.. 3,4,5,6,7,8,9(前两个值发生了什么？)

输入类似的东西时:7,3,5,1,9,2

out只有7,9(所以它不能处理超过一个的值... oO)

附加信息:

typedef struct cellT {
    int value; …

所以我有一个问题，我该如何排序这个列表：

['Pera','mela','arancia','UVA']

像这样：

['arancia','mela','Pera','UVA']

在练习中，它说使用sorted()带有 cmp 参数的函数。