标签: sorted

我有一个数字列表:

myList = [1, 2, 3, 100, 5]

现在,如果我对此列表进行排序以获取[1, 2, 3, 5, 100].我想要的是排序顺序中原始列表中元素的索引,即[0, 1, 2, 4, 3] --- ala MATLAB的sort函数,它返回值和索引.

该文档不保证.是否还有其他记录的地方？

我猜它可能是稳定的,因为列表上的排序方法保证是稳定的(注意第9点:"从Python 2.3开始,sort()方法保证稳定"),并且排序在功能上类似.但是,我无法找到任何明确的消息来源.

目的:在两个记录中主键相等的情况下,我需要根据主键和辅助键进行排序.如果sorted()保证稳定,我可以对辅助键进行排序,然后对主键进行排序并获得我需要的结果.

PS:为了避免任何混淆,我使用稳定的意思是"如果它保证不改变比较相等的元素的相对顺序,则排序是稳定的".

我很困惑,我找不到快速的答案.我基本上在Java中寻找一个实现java.util.List接口的数据结构,但它以排序顺序存储其成员.我知道你可以使用普通ArrayList并使用Collections.sort()它,但我有一个场景,我偶尔会添加并经常从我的列表中检索成员,我不希望每次检索成员时都要对它进行排序,以防万一新增了一个.有人能指出我存在于JDK甚至第三方库中的这样的东西吗？

编辑:数据结构将需要保留重复.

答案摘要:我发现所有这些都非常有趣并且学到了很多东西.Aioobe尤其值得一提,因为他坚持不懈地努力实现上述要求(主要是支持重复的有序java.util.List实现).我已经接受了他的答案,因为我提出的问题是最准确的,而且最让我发现的是我正在寻找的内容的影响,即使我问的不完全是我所需要的.

我要求的问题在于List接口本身以及接口中可选方法的概念.引用javadoc:

该接口的用户可以精确控制列表中每个元素的插入位置.

插入排序列表无法精确控制插入点.然后,你必须考虑如何处理一些方法.就拿add例如:

public boolean add(Object o)

 Appends the specified element to the end of this list (optional operation).

Run Code Online (Sandbox Code Playgroud)

你现在处于令人不安的境地:1)打破合同并实现添加的排序版本2)让add一个元素添加到列表的末尾,打破你的排序顺序3)add抛出(作为其可选)抛出一UnsupportedOperationException和实施这增加了在一个有序的物品的另一种方法.

选项3可能是最好的,但我发现它有一个你不能使用的添加方法和另一个不在界面中的sortedAdd方法令人讨厌.

其他相关解决方案(无特定顺序):

• java.util.PriorityQueue可能比我要求的最接近我所需要的.在我的情况下,队列不是对象集合的最精确定义,但从功能上来说,它可以完成我需要的所有内容.
• net.sourceforge.nite.util.SortedList.但是,这个实现通过在add(Object obj)方法中实现排序来打破List接口的契约,并且奇怪地具有无效方法add(int index, Object obj).一般共识表明throw new UnsupportedOperationException()在这种情况下可能是更好的选择.
• Guava的TreeMultiSet支持重复的集合实现
• ca.odell.glazedlists.SortedList 此类在其javadoc中附带警告:Warning: This class breaks the contract required by List

我正在创建一个类,其中一个方法将新项插入到排序列表中.该项目将插入已排序列表中的已更正(已排序)位置.我不能使用比其他任何内置列表函数或方法[],[:],+,和len虽然.这是让我感到困惑的部分.

解决这个问题的最佳方法是什么？

我想要一个订购的子对象(这里是cat-kitten示例)的集合.并继续增加新元素的顺序.

@Entity 
public class Cat {
  @OneToMany(mappedBy = "cat", cascade = CascadeType.ALL)
  @OrderBy("name ASC")
  private List<Kitten> kittens;

  public void setKittens(List<Kitten> kittens) { this.kittens = kittens; }
  public List<Kitten> getKittens() { return kittens; } 
}

当我这样做时cat.getKittens.add(newKitten),名称将被打破.

是否有可能让hibernate完成保持集合总是有序的工作？通过使用@Sort hibernate注释？
@Sort的缺点在于它迫使你实现Comparable接口......什么是正确的'纯JPA'方法呢？将所有内容保存到数据库并重新加载？合并@ OrderBy和@Sort是否合理？

到目前为止,更新解决方案是将@OrderBy和@Sort结合起来.@OrderBy导致ORDER BY生成的SQL中的一个子句更好的性能(我假设java在插入到已排序的容器时再次"排序",但是这应该快得多,因为元素已经排序了)@Sort with an an实现的Comparable接口导致始终排序的容器.请注意,我现在使用SortedSet而不是List.这里更新的代码:

@Entity 
public class Cat {
  @OneToMany(mappedBy = "cat", cascade = CascadeType.ALL)
  @OrderBy("name ASC")
  @Sort(type = SortType.NATURAL)
  private SortedSet<Kitten> kittens;

  public void setKittens(SortedSet<Kitten> …

我需要在Java中有一个自动按值排序的映射 - 这样当我添加新的键值对或更新现有键值对的值时,它会随时保持排序,甚至删除一些条目.

还请记住,这张地图将会非常庞大​​(数百万,甚至是数百万条的大小).

所以基本上我正在寻找以下功能:

假设我们有一个实现上述功能的"SortedByValuesMap"类,我们有以下代码:

SortedByValuesMap<String,Long> sorted_map = new SortedByValuesMap<String, Long>();
sorted_map.put("apples", 4);
sorted_map.put("oranges", 2);
sorted_map.put("bananas", 1);
sorted_map.put("lemons", 3);
sorted_map.put("bananas", 6);

for (String key : sorted_map.keySet()) {
  System.out.println(key + ":" + sorted_map.get(key));
}

输出应该是:

bananas:6
apples:4
lemons:3
oranges:2

特别是,对我来说真正重要的是能够随时获得具有最低值的条目 - 使用如下命令:

smallestItem = sorted_map.lastEntry();

哪个应该给我'橘子'条目

编辑:我是一个Java新手所以请详细说明你的答案 - 谢谢

EDIT2:这可能会有所帮助:我正在使用它来计算大文本文件中的单词(对于那些熟悉的人:特别是n-gram).所以我需要建立一个地图,其中键是单词,值是这些单词的频率.但是,由于限制(如RAM),我想只保留X最常用的单词 - 但事先你不能知道哪些是最常用的单词.因此,我认为它可能起作用的方式(作为近似)是开始计算单词,当地图达到上限(如1 mil条目)时,将删除最不频繁的条目,以便将地图的大小保持为总是1密耳.

我有一个由JSON组成的文件,每行一行,并希望通过update_time对文件进行排序.

示例JSON文件:

{ "page": { "url": "url1", "update_time": "1415387875"}, "other_key": {} }
{ "page": { "url": "url2", "update_time": "1415381963"}, "other_key": {} }
{ "page": { "url": "url3", "update_time": "1415384938"}, "other_key": {} }

想要输出:

{ "page": { "url": "url1", "update_time": "1415387875"}, "other_key": {} }
{ "page": { "url": "url3", "update_time": "1415384938"}, "other_key": {} }
{ "page": { "url": "url2", "update_time": "1415381963"}, "other_key": {} }

我的代码:

#!/bin/env python
#coding: utf8

import sys
import os
import json
import operator

#load json from file …

如果我创建一个使用整数作为键的Python dict,我可以安全地假设迭代dict将根据键值按顺序检索项目吗？

即会

my_dict = {}
for x in range(0,100):
  my_dict[x] = str(x)

for item in my_dict.items():
  print item

总是导致按键值顺序打印列表？

我今天接受了采访,这个人问我这个问题:

如何轻松找到循环排序数组中的项目

由于我不知道答案,我试图找到解决方案.这就是我所拥有的:

谢谢

<?php


function searchincircularsorterlist($a, $len, $num) {
    $start=0;
    $end=$len-1;
    $mid = 0;
    while($start<$end) {
        $mid=$start+$end/2;
        if ($num == $a[$mid]) {
            return $num;
        }
        if($num<$a[$mid]) {
            if($num<$a[$start] && $a[$start]<=$a[$start+1])
            $start=$mid++;
            else
            $end=$mid--;
            }
        else {
            if($num>$a[$end] && $a[$end-1]<=$a[end])
            $end=$mid--;
            else
            $start=$mid++;
        }
    }
    if ($start == $end && $num == $a[$start]) {
        return $num;
    }
    return -1; 
}

$array = array(7,8,9,0,1,2,3,4,5,6);
var_dump(searchincircularsorterlist($array,sizeof($array),4));

我正在尝试使用循环排序的数组但由于某种原因它不起作用.我的代码出了什么问题？

我最近将我的简历发送给一家雇用PHP开发人员的公司.如果我有足够的经验,他们会给我发回一个要解决的任务.

任务是这样的:

你有一个10k独特元素的数组,排序后代.写入生成此数组的函数,然后编写三个不同的函数,将新元素插入到数组中,插入数组之后仍将按顺序排序.编写一些代码来测量这些功能的速度.您不能使用PHP排序功能.

所以我编写了函数来生成数组和四个函数来将新元素插入到数组中.

/********** Generating array (because use of range() was to simple :)): *************/

function generateSortedArray($start = 300000, $elementsNum = 10000, $dev = 30){
    $arr = array();
    for($i = 1; $i <= $elementsNum; $i++){
        $rand = mt_rand(1, $dev);
        $start -= $rand;
        $arr[] = $start; 
    }
    return $arr;
}

/********************** Four insert functions: **************************/

// for loop, and array copying
function insert1(&$arr, $elem){
    if(empty($arr)){
        $arr[] = $elem;
        return true;
    }
    $c = count($arr);
    $lastIndex = $c - 1;
    $tmp …